Оцінка похибки і міра обумовленості

Припустимо, що матриця системи лінійних рівнянь і вектор правих частин задані неточно і замість пред'явленої до розв’язку системи

AХ=b                           (3.30)

у дійсності розв’язується деяка інша система

A₁X=b₁,                         (3.31)

де A₁=A+  , b₁=b+ . Позначимо розв’язки (3.30) і (3.31) через X і X₁ відповідно. Оцінимо похибку розв’язку z = X₁ - X. Підставимо вирази для A₁, b₁ і X₁ у (3.31)

(A+  ) (X+z) = b + .

Віднімаючи (3.30), одержимо

A z + ^.x + ^.z = ,

z = A^-1 (  -  ^.x - ^. z),

||z||<=||A^-1||^.(|| || + || || ^. ||x|| + ||  || ||z||). (3.32)

Якщо малі ||  || і ||  ||, то варто очікувати і малості ||z||. Тоді доданок ^. z має більш високий порядок малості. Звідси випливає оцінка похибки

 .                (3.33)

Досить поширений випадок, коли похибка матриці системи істотно менша похибки правої частини; як модель цієї ситуації будемо розглядати випадок точного задання матриці системи. Тоді, вважаючи = 0 у (3.33), маємо

||z||<=||A^-1||^. ||  ||.                       (3.34)

Для якісної характеристики зв'язку між похибками правої частини і розв’язку вводиться поняття обумовленості матриці системи. Абсолютні похибки правої частини і розв’язку системи залежать від масштабів, якими вимірюються ці величини і матриця системи. Тому правильніше характеризувати властивості системи через зв'язок між відносними похибками правої частини і розв’язку. Для відносної похибки розв’язку з (3.34) маємо

.                     (3.35)

Підставляючи оцінку для ||x|| у (3.35), маємо

.                   (3.36)

Величину ||A^-1|A|| = condА називають мірою обумовленості матриці. Величина відносної похибки розв’язку при фіксованій величині відносної похибки правої частини може стати як завгодно великою при досить великій мірі обумовленості матриці. Число обумовленості залежить від вибору норми матриці. Будь-яка норма матриці не менша від її найбільшого за модулем власного значення, тобто ||A||>= max | |. Власні значення матриці A і A^-1 взаємно обернені; тому .

Таким чином, .

Системи рівнянь і матриці з великими значеннями мір обумовленості прийнято називати погано обумовленими, а з малими - добре обумовленими. Отже, при розв’язуванні СЛАР на ЕОМ обов’язково виникають похибки заокруглення. Тому фактично маємо розв’язок  деякої іншої системи . На практиці важливо знати відносну похибку . Якщо замість  брати модель , тобто  в ЕОМ задається точно, то з попередніх співвідношень випливає  (  - міра невизначеності розв’язку системи при неточних вхідних даних).

Якщо брати систему , в якій збурені лише елементи , а b – точне, то, використовуючи співвідношення - = () , дістаємо (;

cond .

Лема. Якщо С-квадратна матриця така, що , то існує (І+С)^-1, причому ||(І+С)^-1 || .

Доведення.

Оскільки  , СЛАР   має лише тривіальний розв’язок, що й означає невиродженість матриці І+С.

Теорема. Нехай А – невироджена квадратна матриця. Тоді, якщо X та  є відповідно розв’язками систем AХ=b та , де Ã=А+ΔА , причому , то можлива оцінка .

Доведення. Оскільки , то внаслідок леми існує  причому

Знайдемо

 дістаємо шукане.

Приклад реалізації чисельного алгоритму розв’язання СЛАР на псевдокоді.

//Meтод Зейделя. Вважаємо, що умова збіжності методу перевірена

//повертає норму матриці. А – матриця

NormaMatrix(A): 

1 temp:=0

2 for i:=1 to A.lengthi do

3 sum:=0

4 for j:=1 to A.lengthj do

5 sum+=abs(A[i,j])

6 done

7 if sum>temp then temp:=sum

8 fi

9 done

10 return temp

End

//повертає норму вектора. В – вектор

NormaVector(B):

1 sum:=0

2 for i:=1 to B.length do

3 sum+=sqr(abs(B[i]))

4 done

5 return sqrt(sum)

End

//повертає обернену матрицю до даної A0 з точністю eps

gaussinv(A0,eps):

//доступна в модулі naz.pas

end

//розв’язує систему методом Зейделя

//A – матриця коефіцієнтів

//B – стовпець вільних членів

//X – вектор відповідей

//eps – точність обчислень

// змінні, що обчислюються, але не повертаються функцією як
// результат можуть бути використані в конкретних реалізаціях // алгоритму

Solve_Zeidel(A,B,X,eps):

1 n:=A.lengthI;

2 for i:=1 to n do //AX=B приводимо до вигляду X=CX+D

3 for j:=1 to n do

4 if i<>j then

5 С[i,j]:=(-1)*A[i,j]/A[i,i]

6 else С[i,j]:=0

7 fi

8 done

9 done

10 delta:=(1-NormaVector(С))*eps/NormaVector(С)

11 for i:=1 to n do //обчислюємо A^-1

12 for j=1 to n do

13 A0[i,j]:=A[i,j]

14 done

15 done

16 gaussinv(A0,eps)

17 condA:=norma(A)*norma(A0)

18 fault:=(condA*((0.01/norma(B))+(0.01/norma(A))))/(1-
(condA*0.04)/norma(A)); //обчислюємо похибку

19 for i:=1 to n do

20 X[i]:=B[i]

21 done

22 k:=0

23 repeat //ітераційний процес

24 k++

25 maxr:=0

26 r:=0

27 f or i:=1 to n do

28 xk:=X[i]

29 s:=0

30 for j:=1 to n do

31 s+=C[i,j]*X[j]

32 X[i]:=s+D[i]

33 done

34     r:=abs(xk-X[i])

35      if maxr<r then

36 maxr:=r

37 fi

38 done

39 until maxr<=delta;

end

Питання і завдання до теми

  “Розв’язання систем лінійних алгебраїчних рівнянь точними методами”

1 Норми векторів і матриць. Абсолютна й відносна похибки вектора.

2 Обумовленість задачі розв’язання системи лінійних алгебраїчних рівнянь. Оцінка похибки розв’язку за похибками вхідних даних: .

3 Метод Гауса (схема єдиного ділення):опис методу, трудомісткість методу.

4 Метод Гауса з вибором головного елемента за стовпцем (схема часткового вибору): опис методу, його обчислювальна стійкість.

5 Застосування методу Гауса для розв’язання інших задач обчислювальної алгебри.

6 Метод прогонки з тридіагональною матрицею: опис методу, умови його застосування і переваги.

7 Трудомісткість методу прогонки.

8 Матрична форма запису методу Гауса.

9 LU-розкладання матриці. Теорема про можливості застосування LU- розкладання (без доведення).

10 Застосування методу LU- розкладання для розв’язку задач обчислювальної алгебри.

11 Стратегії вибору провідного елемента в методі Гауса.

12 Метод Гаусса із частковим вибором у матричній формі.

13 Обчислити норми векторів:a) , a=(-3, 0, 4, -5); b) , a=(2, 6, 0); c) , a=(-13, 7, -4,

14 Обчислити норми матриць

       a)  , де A=  ,

        b)  , де A=  ,     

      c)  , де A=  .

15 Чи є вираз  нормою вектора ?

16 Довести властивість норм матриць  й : .

17 Нехай . Довести, що , тоді й тільки тоді, коли , де - власні значення матриці .

18 Перевірити справедливість властивостей числа обумовленості:
 a) , b) ,

c) .

19 Оцінити кількість правильних значущих цифр розв’язку системи лінійних алгебраїчних рівнянь, якщо матриця системи  задана точно, елементи вектора правих частин задані із трьома правильними значущими цифрами, а .

 

Питання і завдання до теми “Розв’язання систем лінійних алгебраїчних рівнянь ітераційними методами”

 

1 Розв’язати систему  методом простої ітерації (методом Якобі) з точністю 0.01.

2 Зробити 3 ітерації за методом Зейделя, попередньо перетворивши системи до вигляду, зручного для ітерації. За початкове наближення взяти нульовий вектор. Зобразити графічно поведінку ітераційного процесу. Проаналізувати отримані результати з погляду збіжності (розбіжності) методу.

, ,

3 Перетворити систему до вигляду, зручного для ітерації:

Перевірити виконання достатньої умови збіжності.

4 Переконатися в тім, що якщо A - нижня трикутна матриця, з ненульовими діагональними елементами, то метод Зейделя збігається за одну ітерацію.

5 Переконатися в тім, що якщо A - діагональна матриця з ненульовими діагональними елементами, то метод Зейделя збігається за одну ітерацію.

6 Переконатися в тім, що якщо A - верхня трикутна матриця, з ненульовими діагональними елементами, то метод Зейделя збігається за скінченне число ітерацій. Знайти цю кількість ітерацій.

7 При яких значеннях  і  метод простої ітерації, застосований для розв’язання системи  з  і деяким вектором , збігається?

8 Нехай система  розв’язується методом Якобі , n =0,1,…... Показати, що достатня умова збіжності методу  (при  й ) еквівалентна умові діагональної переваги матриці .

У задачах 9-13 передбачається, що ітераційні методи розв’язання системи  записані в канонічній формі , n=0,1,…, де  й  - ітераційні параметри.

9 Нехай всі власні значення матриці A дійсні й додатні. Довести збіжність методу  при   з будь-якою матричною нормою.

10 Нехай A - матриця простої структури й всі власні числа , m >0. Довести, що ітераційний метод із задачі 9 збігається при .

11 Довести, що для систем  2-го порядку метод простої ітерації (метод Якобі)

              

 і метод Зейделя:

      

збігаються і розбігаються одночасно. Тут , -діагональна матриця, - нижня трикутна матриця, - верхня трикутна матриця.

12 Довести, що для методу Зейделя необхідною й достатньою умовою збіжності є така умова: всі корені  рівняння

      

за модулем повинні бути менше 1. Тут ,  – елементи матриці  вихідної системи .

13 Довести, що якщо , то справедлива оцінка

, , де  й - мінімальне й максимальне власні значення матриці .

Розділ 4