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


 

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

73328. Додавання і віднімання дробів з різними знаменниками 1.06 MB
  Познайомитися з правилом додавання і віднімання звичайних дробів з різними знаменниками, формувати навички застосування правила при вирішенні типових вправ ; удосконалювати вміння приводити дроби до НСЗ, скорочувати їх, виділяти цілу частину з неправильного дробу;
73330. Урок з математики з елементами українознавства. Розв’язування рівнянь 75.5 KB
  Тема уроку: Розв’язування рівнянь. Мета уроку: Навчальна: узагальнити і закріпити знання учнів про рівняння; Вдосконалювати вміння і навики розв’язувати рівняння на основі залежностей між компонентами арифметичних дій; Розвивальна: Розвивати обчислювальні навики; Розвивати логічне мислення уважність та спостережливість пізнавальний інтерес; Виховна: виховувати почуття любові до України до рідної мови;виховувати інтерес до предмета; Виховувати працелюбність наполегливість...
73331. Повторення складу чисел 5 і 6. Складання рівностей за малюнками. Обчислення значень виразів, що містять додавання, за допомогою предметних малюнків 279.77 KB
  Мета: повторити всі варіанти складу чисел 5 і 6; вправляти у складанні прикладів за малюнками, у розпізнаванні геометричних фігур; вдосконалювати обчислювальні навички; розвивати мислення, навички каліграфічного письма; виховувати старанність.
73333. Створення нумерованих та маркованих списків. Настроювання параметрів сторінок. Створення колонтитулів 860.57 KB
  Мета уроку: сформувати поняття: нумерований і маркований списки; колонтитули; розглянути: способи створення нумерованих маркованих та багаторівневих списків; особливості настроювання параметрів сторінок; формувати вміння: створювати нумеровані й марковані списки; створювати колонтитули; застосовувати набуті знання на практиці; розвивати: творчі здібності; критичне та аналітичне мислення; навчити: застосовувати вміння створювати списки при оформленні тексту; настроювати параметри сторінки. Очікувані...
73335. Мова як особлива система знаків, її місце серед інших знакових систем. Проблеми взаємодії мови і культури, мови і соціуму. Роль мови у формуванні й самовираженні особистості 102.11 KB
  Мова як особлива система знаків її місце серед інших знакових систем. Що не річка то мова знад СлавутиДніпра: українська чудова як сопілкова гра Д. Мова це сукупність усіх слів усіх граматичних форм усіх особливостей вимови всіх людей За Г. Мова це історія і сучасність це кожна людина і народ це інструмент який допомагає людині в її практичній щоденній діяльності тобто виступає знаряддям спілкування і водночас це й засіб проникнення в глибини історичної пам’яті народу це збереження духовних надбань нації для...