69319

Аналіз похибок розв’язування СЛАР

Лекция

Математика и математический анализ

Аналіз похибок через число обумовленості матриці Нехай обчислене значення x помилка розв’язку ε = b відхил або нев’язка розв’язку системи рівнянь x = b. Нев’язка може бути малим а помилка розв’язку великою. 52 cond = 1 число обумовленості матриці що дорівнює максимально...

Украинкский

2014-10-03

336 KB

7 чел.

Лекція 3. Аналіз похибок розв’язування СЛАР

Аналіз похибок через число обумовленості матриці A

Нехай обчислене значення, (x - ) — помилка розв’язку, ε = b - Aвідхил (або нев’язка) розв’язку системи рівнянь Ax = b. Нев’язка може бути малим, а помилка розв’язку — великою. Розглянемо загальний випадок, коли матриця A задана точно, а вектор b — з деякою абсолютною похибкою b .

Тоді можна знайти залежність відносної похибки норми вектора рішення від відносної похибки норми вектора правої частини b:

перемноживши ці дві нерівності, отримуємо

(2.52)

В формулі (2.52) condA = ||A||||A - 1|| — число обумовленості матриці A , що дорівнює максимально можливому коефіцієнту підсилення відносної похибки від правої частини при розв’язку системи.

Нехай тепер вектор b заданий точно, а матриця A — з похибкою A, тоді знаходимо залежність відносної похибки норми вектора рішення від відносної похибки норми матриці коефіцієнтів матриці:

 (2.53)

З урахуванням скінченності разрядної сітки комп’ютерного слова навіть, якщо A і b відомі неточно, то

(2.54)

де u = (1/2)10 1 - t — відносна похибка запису мантиси у розряднiй сітці(t — розрядність).

Відносна помилка розв’язку мала, якщо мале condA.

Приклад 2.8.

Використовуючи метод Гауcса для рішення лінійної системи з А і , наведеними нижче

отримаємо замість точного рішення х = [2 - 2]T наближене рішення

;

нев’язка якого  = [ - 10 - 8 10 - 8]T .

Це сталося тому, що обчислювання досить сильно залежать від помилок округления:

Для даного прикладу потрібна точність завдання елементів матриці aij не менша 10 - 8, тому що задача погано обумовлена. Дійсно, в розглянутому прикладі

Покажемо зв'язок числа обумовленості condA з власними значеннями матриці  ,для якої проведено згідно формули (1.8) перетворення до діагональної форми A = Q1DQ2T, де D — діагональна матриця , Q1, Q2 — ортогональні матриці, сформовані з власних векторів матриці . Відомо, що ортогональні матриці не змінюють модуля вектора, тобто його квадратичної норми:

тому

(максимальне власне значення).

Тобто квадратична норма матриці А обмежена її найбільшим власним значенням:

 (2.55)

Розглядаючи подібним же чином ортогональне перетворення оберненої матриці

A - 1 = Q2D - 1QT1, отримаємо

Це дозволяє остаточно записати, що

 (2.56)

2.5.2. Ітераційне покращення розв’язку

При розв'язанні рівняння Ax = b виникає нев’язка A(x - ), який дорівнює

 

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

(2.57)

Якщо nucondA  0,1, то процес збіжний, і можлива оцінка

(2.58)

Складність такого уточнення згідно виразу (2.57) при вже відомих матрицях L і U дорівнює fn(δx) = n2 + 2∙1/2n2 = 2n2.

Приклад 2.9.

Задана система лінійних рівнянь

має точне рішення : x = [1 1 1] T  при використанні для мантиси п’яти розрядів t = 5.

Виконуючи LU–розклад, знаходимо:

Проводимо уточнення розв’язку, скориставшись процедурою (2.57):

Далі обчислюємо A, використовуючи t = 10 розрядів, і знаходимо значення нев’язку
 (1)

Послідовність покращень вектора рішень згідно (2.57) наводиться нижче в табл..2.2.

Таблиця 2.2. Ітераційне покращення рішення

x (i

1

1,03345

0,89673

1,06667

2

1,00136

0,99628

1,00243

3

1,00005

0,99986

1,00009

4

1,00000

1,00000

1,00000

Користуючись формулою (2.66) оцінюємо число обумовленості вирішуємої задачі:

2.5.3. Метод діагональної модифікації для поліпшення рішення

Це — метод розв’язку погано обумовлених систем, що можуть утворитися при лінеаризації нелінійних математичних моделей. Попереднє упорядкування може буди спотворене на наступному кроці лінеаризації , тому що головний елемент, який визначається похідною від нелінійною функції, змінюється по значенню, наближаючись до нуля. Нове упорядкування не гарантує його збереження на наступному кроці обчислювань. Метод діагональної модифікації дозволяє відмовитись від переупорядкування і полягає в корекції матриці, отриманні з її допомогою проміжних розв’язків і відновлення дійсного (істинного) розв’язку по проміжним.

Якщо на j–му кроці LUрозкладу чи виключення Гаусса головний елемент akk(j) дуже малий, модифікуємо матрицю

Aj = Aj + ekgkekT,

де gk — константа, а ek — транспонований вектор розмірності n, у якого усі елементи нулі і лише к–й елемент дорівнює одиниці . Наприклад , для матриці А4*4 е3 = [0,0,1,0]T .

Визначимо первинну матрицю через модифіковану:

Aj = Aj [I - gk(Aj) - 1ekekT].

Нехай Z = (Aj) - 1ek  ,звідси Aj Z = ek . (2.59)

Тоді X = Aj - 1b = [I - gkZekT] - 1(Aj) - 1b = [I - gkZekT] - 1X,

де X = (Aj) - 1b проміжний розв’язок системи

AjX = b. (2.60)

Для знаходження оберненої матриці [I - gkZekT] - 1 скористаємося формулою Хаусхолдера, яка зв’язує прямі і обернені матриці, що відрізняються елементами рядка чи стовпця:

Використовуючи її, запишемо

 

де zk = ekTZ.

Тоді  (2.61)

тобто дійсне рішення формується комбінацією двох рішень (2.59) і (2.60) , отриманих з модифікованою матрицею.

Приклад 2.10.

Задана система лінійних рівнянь з матрицею и вектором правої частини:

для якої існує точне рішення, яке дорівнює Х = [ - 4/9, 25/9, 17/9,24/9]T .

Припустимо, що на другому кроці LUрозкладу здійснено модифікацію з gk = 3:

Розв’язуємо нову систему рівнянь A2XT = [1,2,3,4]Tі знаходимо рішення:

X = (2/33, - 25/33,29/33,63/33)T.Знаходимо також рішення Z із розв’язку рівняння A2Z = [0,1,0,0,]T, Z = (2/33,8/33, - 4/33, - 3/33)T;

звідки

Комбінуючи два отриманих рішення згідно з (2.61), остаточно знаходимо

.

2.6. Розв’язання перевизначених систем рівнянь

В інженерній практиці зустрічається необхідність розв’язку лінійних систем рівнянь (розріджених чи не розріджених)

Ax = b,

де A — прямокутна матриця [m x n].Наприклад, це трапляється при апроксимації поліномом експериментальних даних, обсяг яких перевищує порядок вибраного полінома.

Така система має безліч рішень, але можна вибрати серед них таке, що мінімізує нев’язок рішення

= b - Ax

Можна довести, що якщо  задовольняє умові ортогональності

At(b - At) = 0,

то для будь–якого іншого розв’язку у виконується нерівність ||b - Ax||2 < ||b - Ay||2.

Це можна зробити, скористувавшись оцінками квадратичної норми для нев’язок x = b - Ax, y = b - Ay, записавши

 (2.62)

З урахуванням умови ATε = 0 при піднесенні рівняння (2.62) до квадрату отримаємо:

Тому вхідне перевизначене рівняння приводиться до так званої нормальної форми помноженням правої і лівої його частин на транспортовану матрицю коефіцієнтів цього рівняння :

 (2.64)

де

Матриця С неособлива, якщо стовпці матриці А лінійно незалежні. Підрахунок добутків ATA і ATb потребує 1/2n(n + 1)m + nm = 1/2nm(n + 3) операцій. Саме розв’язання виконується за n3/6 операцій .

Приклад 2.11.

Знайдемо нормальну форму заданого рівняння:

Із рішення нормального рівняння

знаходимо невідомі x3 = 3, x2 = 7/4, x1 = 5/4.

Можна показати, що нев’язка ε = 1/4 ( - 1 1 0 2 3 - 3)t ортогональна стовпцям А, тобто εtaj = 0.

Висновки:

1. Розв’язок систем лінійних рівнянь є , по суті, базовою процедурою в пакетах математичного моделювання складних об’єктів і систем, що являють собою основний інструментарій спеціалістів з інформаційних технологій. До рішення лінеаризованих систем рівнянь, як буде показано далі, зводяться практично всі задачі визначення статики, динаміки і статистики складних нелінійних об’єктив і систем, при цьому розв’язок лінеаризованих систем рівнянь ітераційно повторяється сотні і тисячі разів з цілеспрямованою зміною деяких параметрів обчислень ( в задачах статики і динаміки) або з випадковими їх змінами (в задачах статистики). Тому питанням оптимізації базової обчислювальної процедури приділяється велика увага.

2. Переважна по об’єму застосувань задача розв’язку лінеаризованих систем рівнянь зумовлює здебільшого використання методу LU–розкладу, який дозволяє на окремих ітераціях зберегти матрицю коефіцієнтів рівнянь і змінювати лише правую частину рівнянь по результатам, отриманим на попередній ітерації.Для реальних інженерних задач характерні розріджені системи лінеаризованих рівнянь, які містять в структурах матриць своїх коефіцієнтів відносно мале число ненульових елементів, і тому припускають їх записі обробку з допомогою кодуючих списків цих елементів.

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

4. Згадане повторне пере упорядкування можна запобігти, скористувавшись методом діагональної модифікації , який дозволяє провести поточний «ремонт» матриці коефіцієнтів і все же таки знайти шукане рішення.

5. Верхньою границею складності алгоритмів прямих методів розв’язку лінеаризованих рівнянь є число n3, де nрозмірність розв’язуваної системи рівнянь. Однак, для розріджених систем рівнянь, які розглядаються у наступній главі, цей показник набагато нижчий , оскільки він пропорційний числу ненульових елементів матриці коефіцієнтів.

6. Багатопроцесорні ЕОМ вносять ревізію в існуючі оцінки ефективності окремих чисельних методів, отриманих для однопроцесорних ЕОМ, що широко розповсюджені сьогодні. Зокрема, на їх основі успішно можуть використовуватися матричні варіанти методів Гаусса і LU–розкладу, які передбачають переважно операції множення матриць

7. Може статися, що потужній арсенал сучасних чисельних методів не в змозі забезпечити необхідну точність при рішенні якоїсь конкретної системи лінеаризованих рівнянь із–за її поганої обумовленості. Це, як правило, трапляється в наслідок неправильного формування математичної задачі інженером або вченим ( наприклад, завдяки зайвої ідеалізації компонентів системи, бажанню одночасно врахувати власні їй швидкі і повільні рухи, що відрізняються на багато порядків тощо).

Вправи

1. Знайти коефіцієнти параболи y = ax2 + bx + c, яка проходить через точки (2,8 ), (1,3), ( - 2,5).

2. Вирішити систему лінійних рівнянь з заданою матрицею коефіцієнтів A і вектором правої частини b методом Гаусса ,скориставшись алгоритмом п.2.2:

2.2. Знайти визначник матриці A перемноженням ведучих елементів під час використання методу Гаусса ..

2.3. Повторити рішення, використовуючи метод вибору головного елемента по стовпцю і порівняти з результатами 2.1 і 2.2

2.4. Підрахував невязку наближених рішень, провести ітераційне їх уточнення.

3. Вирішити систему лінійних рівнянь з заданою матрицею коефіцієнтів A і вектором правої частини b методом LU–розкладу:

 

3.2. Знайти визначник матриці A;

3.3. Знайти обернену матрицю A - 1.

4. Виконати LU–розклад матриці A

і вирішити систему рівнянь Ax = bi, використовуючи знайдений розклад:

.

5. Знайти точний розв’язок системи Ax = b з матрицею Гильберта:

,

Знайти наближений розв’язок той же системи Ax = b, якщо коефіцієнти матриці Гильберта представлені приблизно з округленням до чотирьох знаків:

.

6. Вирішити систему лінійних рівнянь

методом LU–розкладу без матричних операцій (по п.2.4.1)

7. Для системи лінійних рівнянь

,

знайти обернену матрицю і число обумовленості, користуючись алгоритмом п.2.4.5,

8. Довести можливість застосування методу Холецького до симетричної матриці:

і виконати розклад матриці.

9. Вирішити без переупорядкування лінійну систему

,

скориставшись методом діагональної модифікації при виборі додаткової сталої g11 = 1, і довести, що проміжні рішення будуть [x1]t = [ - 1/6, - 1/3,1/2] і [z]t = [5/6,5/3, - 1/2],а шукане рішення [x]t = [ - 1, - 2,1].

10. Вирішити лінійну систему рівнянь з точністю трьох значущих розрядів:

а) без переупорядкування;

б) з повним переупорядкуванням;

в) з повним переупорядкуванням після зміни масштабу x31 = 105x3.

11. Вирішити перевизначену систему рівнянь що відповідають відомим молекулярним вагам таких оксидів:

Назва оксиду

Молекулярна маса

NO

30,006

N2O

44,013

NO2

46,006

N2O3

76,012

N2O5

108,010

N2O4

92,011

Визначити атомні ваги кисню O і азоту N з похибкою до чотирьох знаків.

12. Вирішити методом LU–розкладу систему лінійних алгебраїчних рівнянь

и знайти число обумовленості condA, а також похибку розв’язку, якщо ||Δb|| ≤ 0,01.

13. Вирішити методом LU–розкладу лінійну систему рівнянь з матрицею Ван–дер–Монда четвертого порядку:

і знайти визначник цієї матриці.

14. Вирішити з допомогою оператора Гауссова виключення системи Mathematica5, реалізованого на основі LU розкладу матриці PA, наступну систему рівнянь, визначник якої відмінний від нуля:

15. Повторити розв’язок системи рівнянь приклада 2.5 методом Холецкого, a = 6, 15, 55, 15, 55, 25555, 255, 976, b = 1,4 - 5 користуючись оператором пакету системи Mathematica5.

In[1] = <<LinearAlgebra`Cholesky`…

Порівняти результати з рішенням, отриманим у прикладі 2.5.

Відповіді

1. Необхідно скласти три рівняння відносно коефіцієнтів полінома і знайти

a = 1,66667, b = 1,, c = 0,333333.

3. [x]t = [2 - 1 3];

; detA = 4

6. 

і [x]t = [6,997900 7,074113 1,431551];

7. 

8. 

10. У першому і третьому випадках вектор розв’язку має значення [x]t = [10 - 5 2 - 1]; 

11. x0 = 15,9993 і xN = 14,0069.

12. [x]t = [ - 1 1 - 1 1];, condA = 4488 і похибка ||δx||/||x|| = 1,36.

13. [x]t = [ - 1 1 - 1 1]; і detA = 288.

14. Для цього треба відкрити пакет Mathematica - 5

In = <<LinearAlgebra `GaussianElimination`

і ввести матрицю системи рівнянь:

In = A = {{1,4, - 5},{12, - 1,10},{4,8, - 3}}; Det[A]
Out = - 273

Виконується LU — розкладу матриці з допомогою оператора

In = A1 = LUFactor[A]
Out = Lu[{{1/12,49/100,273/100},{12, - 1,10},{1/3,25/3,19/3}},{2,3,1}]

Відповідь містить матриці L і U, обчислені виключенням невідомих з вибором головного елементу по стовпцю ( див. параграф 2.3.3).

Тепер можна отримати розв’язок системи рівнянь з матрицею A для будь–якої правої части b:

In = b = {1, - 2, 5}; X = LUSolve[A1,b]
Out = { - 22/39, 44/39, 23/39}

Компактний запис матриць L і U може бути отриманий з допомогою наступного оператора:

In = A1[[1]]
Out = {{1/12,49/100, - 273 - 100},{12, - 1,10}{1/3,25/3, - 19/3}

Вектор p = {2,3,1} визначає порядок слідування рівнянь При виключенні невідомих з вибором головного елемента по стовпцю спочатку відбувається перестановка другого рівняння на місце першого. На другому кроці трете рівняння стає другим і відбувається виключення другої змінної. Вказаним перестановкам відповідає матриця P:

У відповідності з (2.43) отримаємо розклад матриці PA = LU, який з точністю до порядку рядків, що визначається вектором p = {2,3,1}, відбиває компактний запис матриць L і U. Самі матриці можна отримати , помножуючи матрицю A1[[1]] на матрицю перестановок P:

In = lu = P.A1[[1]]
Out = {{12, - 1,10}{1/3,25/3, - 19/3}{1/12,49/100, - 273/100}}

Елементи lu, розташовані вище головної діагоналі і на ній , створюють матрицю U. Матриця L містить елементи матриці lu, які розташовані нижче головної діагоналі. При цьому елементи головної діагоналі цієї матриці дорівнюють 1. Отримаємо матриці L і U. 

In = U = lu*Table[If[ij,1,0], {i, Length[lu]}, {j, Length[lu]}]; MatrixForm[U]

In = L = luU + IdentityMatrix[Length[lu]]; MatrixForm[L]

Для перевірки знайдемо добуток LU:

In = MatrixForm[L.U]

Отримана матриця співпадає з матрицею PA. Відмітимо, що структура матриць L і U у пакеті Mathematica–5 відрізняється від структури цих матриць, прийнятої в формулюванні Наслідку 1. Там матриця U має одиничну діагональ, в Mathematica–5матриця L має одиничну діагональ. і в тому і другому випадках Наслідок 1 справедливий. Наприкінці прикладу перевіряється отриманий вище розв’язок X:

In = Z = {z1, z2, z3}; Solve[A.Z = = b,Z}
Out = {{z1 - 22/39,z244/39,z322/36}}

15. Розкладання по методу Холецького:
У складі пакету
LinearAlgebra є функція декомпозиції Холецького, виклик якої здійснюється наступним оператором

In[1] = <<LinearAlgebra`Cholesky`…

Введемо матрицю системи і вектор правої частини рівняння:

a = 6, 15, 55, 15, 55, 25555, 255, 976
b = 1,4 - 5

Наступний оператор здійснює розкладання по методу Холецького:

h[23]: = V = CholeskyDecomposition[a];MatrixForm[V]
Out[23]/MatrixForm =

Порівнюємо з розкладом цієї матриці, отриманим в прикладі 2.5:

h[24]: = MatrixForm[N[V]]
Out[24]/MatrixForm =

Перевіряємо правильність отриманого розкладу:

h[25]: = A Transpose[V].V
Out[25]: = {{0,0,0},{0,0,0},{0,0,0}}

Використаємо отриманий розклад для розв’язку наступної системи

Uty = b, Ux = y:

h[26]: = y = LinearSolve[Transpose[V],b]
Out[26] =

h[27]: = x = LinearSolve[V,y]
Out[27] =

Перевіряємо правильність отриманого розв’язку:

h[28]: = r = A.x - b
Out[28] = {0,0,0}

PAGE  31


 

А также другие работы, которые могут Вас заинтересовать

59759. Сценарій уроку: Державні символи України 36.5 KB
  Україна то лан пишний І степи і гори І як мені України Щиро не кохати. Вчитель: Діти перед вами прапор України. Тиха музика Вчитель: Діти а що це таке малюнок Герб України Так це герб головний символ нашої держави України.
59760. Виховний захід на тему: Тепло батьківського хліба 69 KB
  Ознайомлювати учнів з минулим нашого народу звичаями нашого краю; прищеплювати учням бережливе ставлення до хліба; виховувати повагу до людей праці. Шановні гості Запрошуємо вас до нашої господпи на хліб та сіль на слово щире та бесіду мудру.
59761. Сценарій виховного заходу Бути українцем (за творчістю Василя Латанського) 88 KB
  ХІД УРОКУ Учитель. У Василя Григоровича щаслива учительська доля: він майстер своєї справи талановитий учитель-словесник відмінник освіти України.
59762. Літературна мандрівка місцями перебування Лесі Українки в Балаклаві 37.5 KB
  Наш край по праву вважають другою колискою таланту Лесі. Крим шанує ім’я однієї з найосвіченіших жінок світу митця з терновим вінком: ім’я Лесі носять вулиці бібліотеки кінотеатри; на Кримській землі встановлено стелу з персонажами Лісової пісні...
59763. День Святого Валентина – тематичне заняття в дошкільному закладі (старша група) 57 KB
  Мета: Виховувати любов до рідних, близьких; повагу до оточуючих людей; товариські і дружні почуття. Вчити дітей оцінювати вчинки товаришів. Формувати у дітей уявлення про те, що добра, чуйна людина завжди прийде на допомогу товаришу.
59764. Суспільно-політичне життя УРСР в 1985-1991 роках 40 KB
  Очікувані результати: після цього уроку учні зможуть аналізувати явища суспільнополітичного життя в зазначений період; характеризувати політику гласності лібералізації спроби провести політичні реформи зростання політичної активності населення; співставляти різні точки зору щодо процесів в роки перебудови в Україні та дає їм власну оцінку визначає вплив політичних процесів в роки перебудова на формування причин розпаду СРСР удосконалити навики роботи по створенню “асоціативного куща†презентації на задану тему сформувати і...
59766. Сполучені Штати Америки. Загальна характеристика 59.5 KB
  He was a seaman and made many sea voyages. In 1492 the King and the Queen of Spain gave him money to go to India. He decided to sail west as he was sure that our planet was round. And after sailing 4000 miles
59767. США в первой половине ХIХ века. Гражданская война в США 44 KB
  Цели: охарактеризовать особенности социально-экономического развития США раскрыть причины гражданской войны ознакомить учащихся с её ходом определить влияние личности А.Линкольна президентом...