x3(k+1) = b31x1(k+1) + b32x2(k+1) + … + b3nxn(k) + c3 ,
. . . . . . . . . . . . . . . . . . . . . . . . . .
xn(k+1) = bn1x1(k+1) + bn2x2(k+1) + bn3x3(k+1) + … + cn .
Объединив приведение системы к виду, удобному для итераций и метод Зейделя в одну формулу, получим
xi(k+1) = xi(k) - aii-1(?j=1i-1aijxj(k+1) + ?j=1naijxi(k) - bi).
Тогда достаточным условием сходимоти метода Зейделя будет
?j=1, j?i n | aij | < | aii |
(условие доминированния диагонали).
Метод Зейделя иногда называют также методом Гаусса-Зейделя, процессом Либмана, методом последовательных замещений.
4. Метод релаксации
Метод последовательной верхней релаксации является одним из наиболее эффективных и широко используемых итерационных методов для решения систем линейных алгебраических уравнений с симметричными положительно определенными матрицами А. Этот метод часто называют SOR-методом. Частично популярность SOR-метода можно объяснить его простотой и тем, что он хорошо известен широкому кругу прикладников.
Суть метода релаксации состоит в следующем. После вычисления очередной компоненты приближения по формуле метода Зейделя
производят дополнительно смещение этой компоненты на величину где параметр релаксации. Таким образом, компонента приближения вычисляется по формуле
5. Метода Ньютона (метод касательных)
Пусть корень уравнения f(x) = 0отделён на отрезке, причем f'(x) и f''(x) непрерывны и сохраняют определённые знаки при . Найдя какое-нибудь n-e приближение корня n (), мы можем уточнить его по Методу Ньютона следующим образом. Пусть,где hn малая величина. Отсюда, применяя формулу Тейлора, получим:
Следовательно,
Внеся эту поправку в формулу (2), получим следующее по порядку приближение корня:
(n=0,1,2…).
Геометрически метод Ньютона эквивалентен замене небольшой дуги кривой y=f(x) касательной, проведенной в некоторой точке кривой. в самом деле, положим для определённости, что f''(x)>0 при и f(b)>0 (рис. 1).
Выберем, например, х0=b, для которого f(x)f''(x)>0. Проведем касательную к кривойy=f(x) в точке B0 (x0, f(x0)).
В качестве 1-го приближения x1 корня возьмем абсциссу точки пересечения этой касательной с осью Ox. Через точку B1(x1, f(x1)) снова проведем касательную, абсцисса точки пересечения которой с Oxдаст нам 2-е приближениеx2 корня и т.д. (рис. 1). Очевидно, что уравнение касательной в точке Bn (xn, f(xn)) (где n=0,1,2…) есть
Полагая, что у=0, x=xn+1,получим формулу (3):
.
Заметим, что если в нашем случае положить х0=a и, следовательно, f(x)f''(x)<0, то, проведя касательную к кривой y=f(x)в точкеA(a, f(a)), мы получили бы точку x1' (рис. 1), лежащую вне отрезка [а, b], т. е. при этом выборе начального значения метод Ньютона оказывается непрактичным. Таким образом, в данном случае «хорошим» начальным приближением х0 является то, для которого выполнено неравенство
(4)
Докажем, что это правило является общим.
Теорема. Если f(a)f(b)<0, причем f'(x) и f" (х) отличны от нуля и сохраняют определенные знаки при , то, исходя из начального приближения удовлетворяющего неравенству (4), можно вычислить методом Ньютона (формула (3)) единственный корень уравнения (1) с любой степенью точности.
Доказательство. Пусть, например, f(a)< 0, f(b)>0, f'(x)>0, f''(x)>0 при (остальные случаи рассматриваются аналогично). Согласно неравенству (4) имеем f(x0) >0 (например, можно принять х0 = b).
Методом математической индукции докажем, что все приближения xn>(n = 0, 1, 2,...) и, следовательно, f(xn)>0. В самом деле, прежде всего, x0 >.
Пусть теперь xn>. Положим
Применяя формулу Тейлора, получим:
где <cn<xn.
Так как f''(x)>0, то имеем:
и, следовательно,
что и требовалось доказать.
Из формулы (3), учитывая знаки f(xn) и f'(хn), имеем хn+1 < хn (n = 0, 1, ...), т. е. последовательные приближения x0, x1,…, хn, ... образуют ограниченную монотонно убывающую последовательность. Следовательно, существует .
Переходя к пределу в равенстве (3), будем иметь:
т.е. f()=0. Следовательно, =, что и требовалось доказать.
Поэтому, применяя метод Ньютона, следует руководствоваться следующим правилом: в качестве исходной точки х0 выбирается тот конец интервала (а, b), которому отвечает ордината того же знака, что и знак f"(x).
Замечание 1. Если:
1. функция f(x) определена и непрерывна при ;
2. f(a)f(b)<0;
3. f'(x)при;
4. f"(x) существует всюду и сохраняет постоянный знак, то при применении метода Ньютона для нахождения корня уравнения f(x) = 0, лежащего в интервале (а, b), за начальное приближение x0 можно принять любое значение . В частности, можно взять x0=a или x0=b.
Действительно, пусть, например, f'(x) > 0 при , f"(x )>0 и х0 = с, где .
Если f(с) = 0, то корень = с и задача, таким образом, решена.
Если f(c) > 0, то справедливо приведенное выше рассуждение и процесс Ньютона с начальным значением с сходится к корню.
Наконец, если f(с) <0, то находим значение
Применяя формулу Тейлора, будем иметь:
где --некоторое промежуточное значение между с и х1. Таким образом,f(x1)f''(x1)>0.
Кроме того, из условия f"(x)>0 вытекает, что f' (х) -- возрастающая функция и, значит, f'(x) >f' (а) > 0 при х>а. Следовательно,х1можно принять за начальное значение для процесса Ньютона, сходящегося к некоторому корнюфункции f(x) такому, что>с а. Так как в силу положительности производной f'(х) при х > а функция f(x) имеет единственный корень на интервале (а, +), то=.
Аналогичное рассмотрение можно провести для других комбинаций знаков производных f'(x)и f"(x).
Замечание 2. Из формулы (3) видно, что чем больше численное значение производной f'(x) в окрестности данного корня, тем меньше поправка, которую нужно прибавить к n-му приближению, чтобы получить (n+l)-e приближение. Поэтому метод Ньютона особенно удобно применять тогда, когда в окрестности данного корня график функции имеет большую крутизну. Но если численное значение производной f'(x)близ корня мало, то поправки будут велики, и вычисление корня по этому методу может оказаться очень долгим, а иногда и вовсе невозможным. Следовательно, если кривая y=f(x) вблизи точки пересечения с осью Ох почти горизонтальна, то применять метод Ньютона для решения уравнения f(x) = 0 не рекомендуется.
Оценка погрешности
Для оценки погрешности n-го приближения хn можно воспользоваться общей формулой.
(6)
где m1 -- наименьшее значение |f'(x)|на отрезке [а, b].
Выведем еще одну формулу для оценки точности приближения xn. Применяя формулу Тейлора, имеем:
(7)
где .Так как в силу определения приближения хп имеем
то из (7) находим:
где М2 -- наибольшее значение |f" (х)|на отрезке [а, b].Следовательно, на основании формулы (6) окончательно получаем:
Если процесс Ньютона сходится, то хп- хп-10 при п-->. Поэтому при пимеем:
т.е. «установившиеся» начальные десятичные знаки приближений xn-1иxnначиная с некоторого приближения, являются верными.
Заметим, что в общем случае совпадение с точностью до е двух последовательных приближений хп-1и хпвовсе не гарантирует, что с той же точностью совпадает значение хп и точный корень | (рис. 19).
Установим также формулу, связывающую абсолютные погрешности двух последовательных приближений хп и xn+1. Из формулы (5) получаем:
где . Отсюда, учитывая формулу (3), будем иметь:
и, следовательно,
(9)
Формула (9) обеспечивает быструю сходимость процесса Ньютона, если начальное приближение х0 таково, что
В частности, если
то из формулы (9) получаем:
т.е. в этом случае, если приближение хп имело mверных десятичных знаков после запятой, то следующее приближение хп+1 будет иметь по меньшей мере 2т верных знаков; иными словами, если , то с помощью метода Ньютона число верных знаков после запятой искомого корня удваивается на каждом шаге.
6. Метод наискорейшего градиентного спуска
Распространенным методом минимизации функций большого числа переменных является метод градиентного спуска. Последующее приближение получается из предыдущего смещением в направлении, противоположном градиенту функции. Каждое следующее приближение ищется в виде
Приведенное описание не определяет алгоритм однозначно, поскольку ничего не сказано о выборе параметра. Например, его можно определять из условия минимума величины
В этом случае рассматриваемый метод называют методом наискорейшего градиентного спуска или просто методом наискорейшего спуска.
Для функции, соответствующей системе линейных уравнений с матрицей задача нахождения минимума решается в явном виде. В этом конкретном случае
и
Обозначим через, т.е. положим
Пусть. Вспоминая, что, вычислим. Имеем
Откуда
На рис. 6.8.1 изображены последовательные приближения метода наискорейшего спуска и линии уровня функции F. Итерационный процесс (3), (4) называют методом наискорейшего спуска решения рассматриваемой системы линейных уравнений.
Рис. 6.8.1
Пусть собственные значения матрицы А расположены на, т. е.
Теорема. Приближения метода наискорейшего спуска удовлетворяют соотношению
Доказательство. При произведем одну итерацию оптимального одношагового итерационного процесса
Погрешности итераций связаны соотношением
Пусть - ортонормированная система собственных векторов матрицы . Поскольку, то при всех выполняются соотношения
и, таким образом,
Пусть. Справедливы соотношения
С учетом (7) получаем
Поскольку, то это означает, что
Приближение можно записать в виде (1)
Так как на достигается минимум среди всех приближений вида (1), то. Отсюда следует оценка
а поэтому и справедливость утверждения теоремы. Аналогично (7.9) можно получить неравенство
Хотя на каждом шаге метода наискорейшего спуска уменьшение величины заведомо не меньше, чем у итерационного процесса (6), мы получили примерно одинаковые оценки скорости сходимости.
Однако есть принципиальное различие в этих методах. Для написания итерационного процесса (6) требуется информация о границах спектра. В случае метода (3), (4), такой информации не требуется.
Отметим также то важное обстоятельство, что метод наискорейшего спуска является нелинейным итерационным методом; параметры метода на каждом шаге выбираются в зависимости от полученного приближения.
У метода наискорейшего спуска (3), (4), однако, есть следующий недостаток по сравнению с простейшим процессом (6). При нахождении каждого следующего приближения он требует не одной, а двух трудоемких операций умножения матрицы на вектор.
Двукратного умножения матрицы на вектор при каждой итерации можно избежать следующим образом. Обозначим и перепишем (3) в виде
Вектор называется невязки. Умножая (8) слева на А и вычитая, получим
Формулу (4) для определения можно записать в виде
В процессе итерации запоминаются векторы и на каждом шаге последовательно вычисляются. В исходном методе наискорейшего спуска (3), (4) погрешность на шаге итерации равносильна возмущению начального приближения и, поскольку процесс сходящийся, ее влияние должно иметь тенденцию к затуханию.