Методы решения алгебраических уравнений

х1 = х0 - f(хо)/ fI (хо)

Применив этот прием вторично в точке M1[ x1; f (x1)], найдем

X2=X1 – f (x1)/(x1)

и т. д. Полученная таким образом последовательность xo, x1,x2 … имеет своим пределом искомый корень.

Для оценки погрешности приближенного значения корня, найденного методом Ньютона, может быть использовано неравенство

| х - ξ | < [f(ξ) ]2/2 × max | fII(х)/ [fI(х) ]3|

[a., b]

3. Комбинированный метод хорд и касательных. Пусть требуется найти действительный корень уравнения f (x)= 0, изолированный на отрезке [a,b]. Предполагается, что f (a) и f (b) имеют равные знаки, а каждая из производных сохраняет определенный знак на отрезке изоляции. Возьмем на отрезке [a,b] такую точку xo, что f (xo) и f” (xo) (при x, принадлежащем промежутку изоляции) имеют одинаковые знаки.

Воспользуемся формулами методов хорд и касательных:

X11=Xo- f (xo) / f1(xo); X12 = a – (b – a ) f (a) / f (b) – f (a).

Величины X11 и X12 принадлежат промежутку изоляции, причем f (X11) и f (X12) имеют разные знаки.

X21=X11- f (x11) / f1(x11); X22=X11-(X12-X11) f (X11) / f (X12) – f (X11).

Точки X21 и X22 на числовой оси расположены между точками X11 и X12, причем f (X21) и f (X22) имеют разные знаки.

Вычислим теперь значения

X31=X21- f (x21) / f1(x21); X32=X21-(X22-X21) f (X21) / f (X22) – f (X21).

Каждая из последовательностей X11, X21, X31, . Xn1, …; X12, X22, X32, …, Xn2, …стремится к искомому корню, причем одна из последовательностей монотонно возрастает, а другая – монотонно убывает. Пусть, например, Xn1 < X< Xn2, тогда 0 < X- Xn-1 < Xn2- Xn2 – Xn1. Задав заранее достаточно малое мы можем, увеличивая n, добиться выполнения неравенства Xn2 – Xn1 < ; следовательно, при этом же значении n будет выполняться неравенство

X – Xn1 < . Таким образом, Xn1 является приближенным значением корня X, вычисленным с погрешностью, не превышающей .

Так, например, для нахождения приближенного значения X с точностью до 0,001 нужно определить n таким образом, чтобы значения Xn1 и Xn2, вычисленные с точностью до 0,001, совпадали.

2. Решение систем линейных алгебраических уравнений. Методом Крамера. Методом Гаусса. Метод Жордана Гаусса. Метод Зейделя

Решение систем линейных алгебраических уравнений – одна из основных задач вычислительной линейной алгебры. Хотя задача решения системы линейных уравнений сравнительно редко представляет самостоятельный интерес для приложений, от умения эффективно решать такие системы часто зависит сама возможность математического моделирования самых разнообразных процессов с применением ЭВМ. Значительная часть численных методов решения различных (в особенности – нелинейных) задач включает в себя решение систем линейных уравнений как элементарный шаг соответствующего алгоритма. Одна из трудностей практического решения систем большой размерности связанна с ограниченностью оперативной памяти ЭВМ. Хотя объем оперативной памяти вновь создаваемых вычислительных машин растет очень быстро, тем не менее, еще быстрее возрастают потребности практики в решении задач все большей размерности. В значительной степени ограничения на размерность решаемых систем можно снять, если использовать для хранения матрицы внешние запоминающие устройства. Однако в этом случае многократно возрастают как затраты машинного времени, так и сложность соответствующих алгоритмов. Поэтому при создании вычислительных алгоритмов линейной алгебры большое внимание уделяют способам компактного размещения элементов матриц в памяти ЭВМ.

К счастью, приложения очень часто приводят к матрицам, в которых число ненулевых элементов много меньше общего числа элементов матрицы. Такие матрицы принято называть разреженными. Одним из основных источников разреженных матриц являются математические модели технических устройств, состоящих из большого числа элементов, связи между которыми локальны. Простейшие примеры таких устройств – сложные строительные конструкции и большие электрические цепи.

Известны примеры решенных в последние годы задач, где число неизвестных достигало сотен тысяч. Естественно, это было бы невозможно, если бы соответствующие матрицы не являлись разреженными (матрица системы из 100 тыс. уравнений в формате двойной точности заняла бы около 75 Гбайт).

Методом Крамера. Известно, что используя матрицы мы можем решать различные системы уравнений, причем эти системы могут быть какой угодно величины и иметь сколько угодно переменных. С помощью нескольких выводов и формул решение огромных систем уравнений становится довольно быстрым и более легким.

В частности, я опишу методы Крамера и Гаусса. Наилегчайшим способом является метод Крамера (для меня ), или как его еще называют – формула Крамера. Итак, допустим, что мы имеем какую-либо систему уравнений

,

в виде матрицы эту систему можно записать таким образом:

A = ,

где ответы будут уравнений будут находится в последнем столбце. Теперь мы введем понятие основного определителя; в данном случае он будет выглядеть таким образом:

= .

Основным определителем как вы уже заметили является матрица составленная из коэффициентов стоящих при переменных. Они также идут в порядке столбцов, т. е. в первом столбце стоят коэффициенты, которые находятся при x, во втором столбце при y, и так далее. Это очень важно, ибо в следующих действиях мы будем заменять каждый столбец коэффициентов при переменной на столбец ответов уравнений. Итак, как я уже говорил, мы заменяем столбец при первой переменной на столбец ответов, затем при второй, конечно это все зависит от того, сколько переменных нам нужно найти.

1 = , 2 = , 3 = .

Затем нужно найти определители 1 , 2 , 3 . Как находится определитель третьего порядка вы уже знаете. А вот здесь мы и применяем правило Крамера. Оно выглядит так:

 Скачать реферат