Вычислительная математика. Лекции

и все последующие векторы x3; x4; : : : ; xk+1; : : : строятся как решения xk+1 линейных алгебраических си-

стем

F 0(xk)(x xk) = F (xk):

Возникают следующие вопросы:

-разрешимы ли эти системы?

-принадлежат ли эти решения области ?

-сходится ли последовательность векторов к решению x ?

-единственно ли это решение в области ?

2.1Вектор-функция.

Для вектора x 2 Vn обозначим

max jxij =k x k :

i

Число k x k называется нормой вектора x. Расстояние между векторами x и y определим как k x y k; последовательность векторов xk сходится к вектору x , если k xk x k! 0 при k ! 1:

Для вектора F (x) норма k F (x) k= max jfi(x)j; норма

i

k F (x + x) F (x) F 0(x) x k=k r(x + x; x) k= 0(k x k);

если частные производные функции fi(x) непрерывны. Для матрицы A = faijgni;j=1 обозначим

Рассмотрим матрицы F0(x) (линейные операторы в векторном пространстве Vn), вычисленные в точках

x00 и x0: F0(x00) и F0(x0):

Определение. Говорят, что оператор F0(x) удовлетворяет условию Липшица с постоянной L, если

k F0(x00) F0(x0) k L k x00 x0 k :

Пусть оператор F0(x) удовлетворяет условию Липшица. Так как матрица

При фиксированных векторах x и x значение fi(x + # x) являются функцией от # : fi(x + # x) = 'i(#): Дифференцируя эту сложную функцию

n

d'i(#) = X @fi(x + # x) xj d# @xj

j=1

8

и интеграл

0j=1

Оценим

0

Эта оценка позволяет определить порядок малости норм k r(x0; x ) k; k r(x1; x ) k; : : : ; k r(xk; x ) k; : : : при построении метода Ньютона.

2.2Порядок сходимости метода Ньютона.

Для непрерывной вектор-функции F (x) рассмотрим последовательность векторов, построенных по правилу

xk+1 = xk F (xk); k = 0; 1; 2; :::

с начальным вектором x0: Если существует lim xk; k ! 1; то по непрерывности функции F (lim xk) = 0: Пусть Bk - последовательность линейных операторов, таких что существуют обратные операторы Bk 1:

Образуем новую последовательность векторов xk:

xk+1 = xk Bk 1F (xk):

Для векторов xk этой последовательности выполнены равенства

Bk(xk+1 xk) + F (xk) = 0:

Если эта последовательность имеет предел x , то F (x ) = 0:

9

В методе Ньютона выбирают Bk = F 0(xk) :

и для этой последовательности

При изучении сходимости метода Ньютона будем предполагать:

-операторы F 0(x) удовлетворяют условию Липшица,

-нормы операторов [F 0(x)] 1 ограничены: k [F 0(x)] 1 k :

Порядок сходимости метода устанавливается в предположении, что xk ! x при k ! 1: Сравним величины k xk x k и k xk+1 x k :

Введем вектор y :

y= F (xk) F 0(xk)(x xk) = F (xk) F 0(xk)(xk+1 xk xk+1 + x ) =

=F (xk) F 0(xk)(xk+1 xk) F 0(xk)(x xk+1) = F 0(xk)(x xk+1):

= [F 0(xk)] 1y:

y = F (x ) F (xk) F 0(xk)(x xk)

и согласно оценке ( )

k F (x ) F (xk F 0(xk)(x xk) k 12L k x xk k2 :

Тогда

k 12L k x xk k2;

и следовательно метод Ньютона - метод второго порядка.

2.3Сходимость метода Ньютона.

Пусть выбрано начальное приближение x0 и x0 внутренняя точка области :

Теорема. Пусть в области :k x x0 k операторы F 0(x) удовлетворяют условию Липшица в постоянной L, существуют обратные операторы [F0(x)] 1 и k [F0(x)] 1 k :

Тогда если

- величина q = 12 L 2m < 1; где m =k F (x0) k;

1

- m P q2j 1 ;

j=0

1

то xk ! x , x 2 ; F (x ) = 0 и k x xk k m P q2j 1:

j=k

Доказательство проводится аналогично доказательству сходимости метода простой итерации решения скалярного уравнения.

Легко устанавливаются неравенства

k xk+1 xk k mq2k 1; k xk+1 x0 k qm(1 + q + q3 + : : : + q2k 1);

обеспечивающие принадлежность точек xk 2 : Из сходимости в себе последовательности fxkg получаем существование предела последовательности fxkg и оценку k x xk k :

Замечание. При дополнительном условии L < 1 решение x системы единственно в области :

10

Глава 3

МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ СЛАУ.

ВВЕДЕНИЕ 1. Линейные векторные нормированные пространства.

В этой главе рассматриваются вещественные линейные векторные пространства. В этих пространствах вводятся различными способами метрика. Как правило метрика определяется нормой k x k вектора x :

(x; y) =k x y k;

и мы получаем полное нормированное векторное пространство.

Обычно рассматриваются три нормированные пространства, в которых норма вектора x(x1; x2; : : : ; xn) равна:

1. k x k1= max jxij;

i

n

P

2. k x k1= jxij;

i=1 n

3. k x k2= (P x2i )1=2: i=1

Для любых этих пар нормированных пространств верны неравенства (эквивалентность норм):

C1 k x kII k x kI C2 k x kII;

где постоянные C1 и C2 зависят от выбора пространств и от размерности вектора x, но не зависят от выбора вектора x.

Пример.

k x kI=k x kII; k x kII=k x k2 :

Ясно, что

Если установлено, что последовательность fxkg сходится к x в одной норме, то она сходится к x в любой другой норме.

2. Линейные операторы в нормированных пространствах. Нормы матриц, нормы операторов.

11

Линейные отображения (линейные операторы) в n-мерном векторном пространстве Vn определяются квадратными матрицами A :

n

X

A = faijgni;j=1; Ax = y; y = y(y1; y2; : : : ; yn); yi = aijxj:

j=1

Рассматривая для вектора x и вектора y разные нормы, мы получим линейные отображения из одного нормированного пространства в другое нормированное пространство. Мы будем предполагать, что для x и Ax выбраны одинаковые нормы: нормы x и Ax согласованы.

Рассмотрим множество S1 векторов, нормы которых равны 1: Координаты этих векторов ограничены. Координаты векторов Ax и значения k Ax k являются непрерывными функциями координат вектора x. Тогда существует sup k Ax k и этот супремум достигается: sup k Ax k= max k Ax k :

k Ax k k A kk x k :

Легко показать, что верны неравенства

k x k1= 1: Легко показать, что

nn

PP

k Ax k22= (Ax; Ax) = (A Ax; x) 0: Матрица A A симметричная, положительная и её собственные числа n вещественны и неотрицательны:

0 1 2 : : : n:

Обозначим через '1; '2; : : : ; 'n соответствующие им собственные векторы:

12

n

A A'i = i'i; ('i; 'j) = 0 при i 6= j, k 'i k2= 1: Любой вектор x представим в виде x = P i; 'i; где

i=1

n

i = (x; 'i), k x k22= P i2: Тогда

i=1

k Ax k22 n k x k22; k Ax k2 p n k x k2; k A k2 p n:

Для вектора 'n 2 S1 норма k A'n k2= p : Таким образом k A k2= j mj; где m- максимальное по модулю собственное число матрицы A:

Эквивалентность норм матрицы.

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

3.Числа обусловленности матрицы.

Пусть матрица A имеет обратную матрицу A 1: Рассмотрим две системы Ax = y и Ax = y + y; где y вариация (погрешность) вектора y: Вариация решения x = A 1 y: Рассмотрим относительную погрешность решения kkxxkk и относительную погрешность kkyykk правой части:

Число (A) =k A 1 kk A k называется числом обусловленности матрицы A в выбранной метрике. Свойства числа обусловленности

1. (A) 1: Так как в любой норме k E k= 1; то

1 =k E k=k A 1A k k A 1 k k A k= (A):

2: ( A) = (A) : ( A) =k ( A) 1 k k A k= j1j k A 1 k j j k A k= #(A):

3. Оценка снизу числа обусловленности матрицы. Рассмотри векторы x и y = A x и векторы x и

y = Ax: Тогда отношение

k xk

kxk (A): k yk

kyk

4. В оценке kkxxkk C kkyykk значение C = (A) уменьшить нельзя.

Действительно, рассмотрим вектор y; такой что k A 1 y k=

=k A 1 k k y k; обозначим x = A 1 y :k x k=k A 1 k k y k :

Рассмотрим вектор x, такой что k Ax k=k A k k x k; обозначим y = Ax : k y =kk A k k x k и k x k= kA1k k y k :

Если (A) >> 1; то говорят, что матрица А и система уравнений Ax = y плохо обусловлены.

Пример

13

Рассмотрим x = (0; 0; :::; 0; 1); и y = Ax = ( 1; 1; :::; 1; 1):

Выберем k x k=k x k1 : k x k1= 1, k y k1= 1; k A k1= n:

Пусть y = (0; 0; :::; 0; "), k y k1= ": Тогда x = "(2n 2; 2n 3; :::; 2; 1; 1). k x k1= "2n 2:

Для числа обусловленности получаем оценку (A) 2n 2 (n = 32): Таким образом матрица A и