85666 (612542), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

(3.2)

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

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

– система линейных уравнений

Рассмотрим вопрос о сходимости метода Ньютона. Точное условие сходимости метода Ньютона для решения систем нелинейных уравнений имеет довольно сложный вид. можно отметить очевидный результат: в достаточно малой окрестности корня итерации сходятся, если матрица Якоби невырожденная, причём сходимость квадратичная.

Приведём ряд теорем, выполнение условий которых должно обеспечивать сходимость метода Ньютона.

Пусть в пространстве выбрана некоторая векторная норма и согласованная с ней матричная норма .

Теорема (о сходимости). Пусть

1. вектор-функция определена и непрерывно-дифференцируема в области

где – решение уравнения (3.1),

2) для всех существует обратная матрица , причём

3)для всех

4)

Тогда метод Ньютона (3.2)

1)

2)

3)

Доказательство. Докажем первое утверждение теоремы с помощью индукции. По условию . Допустим, что . Поскольку , то . Рассмотрим условие 3) теоремы для

.

Согласно формуле (3.2)

,

Кроме того . Тогда предыдущее неравенство принимает вид

Следовательно,

Таким образом, имеет место неравенство

(3.3)

По предположению индукции . Поскольку в силу условия 4)

, то

Это значит, что для , и шаг индукции реализован. Превое утверждение теоремы доказано.

Продолжим доказательство. Положим перепишем оценку (3.3) после умножения на в виде . Покажем, что

(3.4)

Будем рассуждать по индукции. При неравенство (3.4.) очевидно. Допустим, что оно справедливо для некоторого . Тогда

Переход завершен, т.е. неравенство (3.4) справедливо для всех . Перепишем его в исходных обозначениях

Получили утверждение 3). При этом

, т.е. .

Это значит, что имеет место сходимость:

Замечание 1. Неравенство (3.3) при условии означает, что последовательность сходится к решению с квадратичной скоростью.

Замечание 2. Поскольку , то из утверждения 3) следует оценка погрешности метода Ньютона

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

Доказательство. Рассмотрим

Введем и матрицу и матрицу. Очевидно, что F(x,x)= F(x), то есть имеем

(12)

Есть тождества

Тогда.

Вблизи окрестности для любого найдется такое x⁰, что если,. то

Тогда

На начальное приближение x⁰ наложено труднопроверяемое условие.

Т еорема Канторовича. Если функции f_i(x) непрерывны вместе со своими 1 -ми и 2 -ми производными в некоторой выпуклой области G, содержащей точку x⁰ вместе с ее окрестностью и выполнены следующие условия:

в точке x⁰ существует матрица F^-1 такая

то последовательность x^k+1=x^k-f^-1_x(x^k)F(x^k) сходится к . является единственным решением системы f(x)=0 в области и имеет место оценка

Докажем 3 неравенства

а)

б)

в)

б)

в)

т.е. матрица F^-1_x(x⁰)F_x(x¹) невырождена, и

и

F_x(x⁰)(x¹-x⁰)+f(x⁰)=0

Покажем, что при всех k имеют место неравенства:

(А)

Пусть имеет место m=k-1

Повторим неравенства

Неравенство (А) показывает, что в круге R последовательность x^k является фундаментальной, т.е. имеется предел.

О ценим сходимость

т.е.,

устремляя правая часть не меняется,, т.е. при очень хорошая сходимость.

2.3.1 Модификации метода ньютона

1. Вычисления в методе Ньютона гораздо сложнее, чем при простых итерациях, т.к. на каждой итерации требуется находить матрицу производных и решать систему линейных уравнений. Поэтому рекомендуется такой приём: матрица Якоби вычисляется только на начальном приближении. Однако сходимость при этом видоизменении становится линейной, причём обычно не с малой константой, ибо матрица производных на начальной итерации может заметно отличаться от окончательной. Поэтому скорость сходимости заметно уменьшается и требуемое сисло итераций возрастает.

2. В ещё одной модификации итерационную формулу метода Ньютона вводится параметр следующим образом

На каждой итерации находится так, чтобы уменьшить невязку уравнения (3.1), т.е. выполнить неравенство

(3.5)

Проведём обоснование такой процедуры в евклидовой норме.

Ведём в рассмотрение функцию-невязку для уравнения (3.1)

Найдём градиент , используя представление

С этой целью выделим главный член приращения

Следовательно, по определению

Обозначим и найдём производную функции в точке по направлению :

если .

Таким образом, – есть направление спуска для функции в точке для малых . Это значит, что выбор шага согласно условию (3.5) возможен.

2.3.2 Квазиньютоновкие методы

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

Рассмотрим первый из классов, где матрица В_к с размерами п х п аппроксимирует матрицу . Перед началом итераций задают начальную точку а матрицу В_о обычно получают, или допуская, что она является единичной, или аппроксимируя конечно-разностными формулами. Потом для k = 0, 1.... вычисляют

Где — n- мерный вектор, который является параметром рассматриваемого класса методовв. Если взять таким, что равняется ,то будем иметь первый метод Бройдена. Выбор соответствует методу Пирсона, а — симметрическому методу первого ранга.

Во втором из рассматриваемых здесь классов квазиньютоновских методов матрица с размерами п х п аппроксимирует матрицу . Перед началом итерации задают начальную точку х^{0) и матрицу , которая обычно или равна единичной, или является обратной к конечно-разностной аппроксимации . Потом вычисляют

где — n-мерный вектор, который является параметром рассматриваемого класса методов. Конкретный вид вектора отвечает соответствующему методу: например, — второму методу Бройдена, — методу Мак-Кормика.

Заметим, что если задать то можно вести перерасчет не В_к, а матриц по формуле

(3.30)

эквивалентной (3.27). Это требует порядка 0(п²) арифметических действий вместо 0(п³), необходимых для решения системы линейных уравнений .

Как видно из (3.30), между формулами (3.27) и (3.29) имеет место определенная связь. Так.если , то при . Таким образом, один и тот же метод может реализоваться двумя разными формулами (3.27) и (3.29), которые эквивалентные теоретически, но их численная реализация может отличаться по эффективности.

Рассмотрим, например, первый метод Бройдена. Его можно реализовать по формуле (3.27) так, что это потребует в общем 0(n³) арифметических действий. Это оказывается возможным, если подать матрицу В_к в виде произведения , где — ортогональная, а — верхняя треугольная матрица. Действительно, в этом случае решение системы нуждается в только 0(n³) арифметических действий. Имея , на представление матрицы В_к+1, которая удовлетворяет (3.27) в виде , необходимо 0(п²) арифметических действий. Важное преимущество формулы (3.27) перед (3.39) заключается в том, что в (3.27) нет необходимости умножения матрицы на вектор, поскольку

Существуют квазиньютоновские методы, которые учитывают симметричность матрицы Якоби и вырабатывают последовательность симметричных матриц В_к, (или ). Эти методы также можно разделить на два класса. В первом из них матрица В_к аппроксимирует F(х). В отличие от описанного выше класса, который задается формулами (3.26) и (3.27), здесь нужна симметричность матрицы Во, и вместо (3.27) используется формула

Характеристики

Список файлов курсовой работы