Метод исключения Гаусса для решения СЛАУ

1.3 Метод исключения Гаусса для решения СЛАУ

Суть всех методов исключения состоит в приведении исходной системы уравнений к системе более простого вида, для которой легко найти решение. К этим методам можно отнести метод исключения Гаусса, который имеет много вычислительных схем и, как показали исследования, является идеальным алгоритмом для решения СЛАУ.

Рассмотрим сначала самую простую схему – схему единственного деления. Применение схемы единственного деления продемонстрируем на примере СЛАУ 4- го порядка

Разделив первое уравнение системы на , получим

Из второго уравнения системы вычтем первое, умноженное на коэффициент при , то есть на . В результате получаем:

=

Поступая таким же образом с третьим и последующими уравнениями системы, получим

;

;

.

К выделенной системе применим тот же алгоритм, что и к исходной. В результате получаем

Прямой ход метода Гаусса закончен. Из полученной треугольной системы линейных алгебраических уравнений обратным ходом Гаусса отыскиваем вектор решения  по следующим формулам

, , .

  1.4 Вывод формулы пересчета Бройдена

В процессе построения методов Ньютона и секущих решения нелинейного скалярного уравнения  
функция f(x) в окрестности текущей точки  подменяется линейной функцией (аффинной моделью)

. Приравнивание к нулю последней, т.е. решение линейного уравнения , порождает итерационную формулу  для вычисления приближений к корню уравнения.

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

Равенство , переписанное в виде , называют соотношением секущих в  Оно легко обобщается на n -мерный случай и лежит в основе вывода метода Бройдена. Опишем этот вывод.

В n-мерном векторном пространстве  соотношение секущих представляется равенством

,

где  - известные n-мерные векторы,  - данное нелинейное отображение, а  - некоторая матрица линейного преобразования в . С обозначениями ,  соотношение секущих в  обретает более короткую запись . Аналогично одномерному случаю, а именно, по аналогии с формулой , будем искать приближения к решению  векторного уравнения  по формуле . Обратимую n x n-матрицу  в ней нужно подобрать так, чтобы она удовлетворяла соотношению секущих . Но это соотношение не определяет однозначно матрицу : глядя на равенство , легко понять, что при n>1 существует множество матриц , преобразующих заданный n-мерный вектор  в другой заданный вектор  (отсюда - ясность в понимании того, что могут быть различные обобщения одномерного метода секущих).

При формировании матрицы  будем рассуждать следующим образом. Переходя от имеющейся в точке  аффинной модели функции F(x)  к такой же модели в точке   мы не имеем о матрице линейного преобразования  никаких сведений, кроме соотношения секущих . Поэтому исходим из того, что при этом переходе изменения в модели должны быть минимальными. Эти изменения характеризует разность . Вычтем из равенства  определяющее  равенство  и преобразуем результат, привлекая соотношение секущих . Имеем:

Представим вектор  в виде линейной комбинации фиксированного вектора  определенного в , и некоторого вектора t, ему ортогонального: ,

Подстановкой этого представления вектора  в разность  получаем другой ее вид  

Анализируя выражение , замечаем, что первое слагаемое в нем не может быть изменено, поскольку  - фиксированный вектор при фиксированном k. Поэтому минимальному изменению аффинной модели  будет отвечать случай, когда второе слагаемое в  будет нуль-вектором при всяких векторах t, ортогональных векторам , т.е.  следует находить из условия   

Непосредственной проверкой убеждаемся, что условие   будет выполнено, если матричную поправку  взять в виде одноранговой nхn-матрицы .

Таким образом, приходим к так называемой формуле пересчета С. Бройдена