Розв’язування систем лінійних алгебраїчних рівнянь. Абсолютна величина і норма матриці, страница 4

A₁^. x=b₁,                                                    (5)

де  A₁=A+ ,b₁=b+. Позначимо розв’язки (4) і (5) через x і x₁

Оцінимо похибку розв’язку z = x₁ - x.

Підставимо вирази для A₁, b₁ і x₁ у (5)

(A+ ) (x+z) = b +

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

A z + ^.x + ^.z =

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

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

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

 .                             (7)

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

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

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

                                         (9)

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

                                      (10)

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

Таким чином,

.

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

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

  cond.

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

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

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

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

Знайдемо 

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

.Метод Гауcса

Розглянемо задачу розв’язку системи рівнянь:

                         (11)

чи Ax=b, де A - матриця коефіцієнтів системи, x - вектор невідомих, b - вектор правих частин.  Відомо, що розв’язок системи лінійних рівнянь можна виразити за формулами Крамера через відношення визначників. Але обчислення визначника не простіше за розв’язок вихідної системи. Для розв’язку системи порядку n необхідно обчислити (n+1) визначник, тобто обчислення розв’язку за формулами Крамера вимагає в (n+1) раз більше операцій ніж розв’язування системи іншим методом, наприклад методом Гаусса.

Метод Гаусса заснований на приведенні шляхом еквівалентних перетворень вихідної системи (11) до вигляду з верхньою трикутною матрицею.

 с₁₁ ^.  x₁ + c₁₂x₂ + … + c_1n x_n =d₁

                           0     + c₂₂x₂ + …  + c_2nx_n = d₂

  …………………………                               (12)

                          0 + 0 + … + c_n-1,n-1x_n-1 + c_n-1,nx_n = d_n-1

                          0 + 0 +……………...  +0 +c_nnx_n = d_n                  

Тоді з останнього рівняння відразу визначаємо

 .

Підставляючи його в попереднє рівняння, знаходимо x_n-1 і т.д. Загальні формули для отримання розв’язку мають вигляд

       (13)