Бінарна алгебраїчна операція
Химия

Метод прогонки рішення систем з тридіагональними матрицями коефіцієнтів


Метод прогонки рішення систем з тридіагональними матрицями коефіцієнтів

Завантажити реферат: Метод прогонки розв’язання систем з тридіагональними матрицями коефіцієнтів

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

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

bixi-1+cixi+dixi=ri (1)

де i=1,2,…,n; b1 = 0, dn = 0. Такі рівняння називаються триточковими різницевими рівняннями другого порядку. Система (1) має тридіагональну структуру, що добре видно з наступного, еквівалентного (1), векторно-матричного уявлення:

c1 d1 0 0 … 0 0 0 x1 r1

b2 c2 d2 0 … 0 0 0 x2 r2

0 b3 c3 d3 … 0 0 0 x3 r3

. . . . …. . . * … = …

0 0 0 0 … bn-1cn-1 dn-1 xn-1 rn-1

0 0 0 0 … 0 bn cn xn rn

Як і у рішенні СЛАУ методом Гауса, мета позбавиться ненульових елементів у піддіаганальній частині матриці системи, припустимо, що існують такі набори чисел δi та λi (i=1,2,…,n), при яких

xi= δixi+1+ λi (2)

тобто. триточкове рівняння другого порядку (1) перетворюється на двоточкове рівняння першого порядку (2). Зменшити у зв’язку (2) індекс на одиницю та отриманий вираз xi-1= δi-1xi+ λi-1 підставимо в дане рівняння (1):

biδi-1 xi+ bi λi-1+ cixi+ dixi+1= ri

звідки

xi= -((di /( ci+ biδi-1)) xi-1+(ri — bi λi-1)/( ci — bi δi-1)).

Остання рівність має вигляд (2) і точно з ним співпадати, інакше кажучи, уявлення (2) матиме місце, якщо при всіх i=1,2,…,n виконуються рекурентні співвідношення

δi = — di /( ci+ biδi-1) , λ i=(ri — bi λi-1)/( ci — bi δi-1) (3)

Легко бачити, що, в силу умови b1=0, процес обчислення δi λi може бути початий зі значень

δ1 = — d1/c1, λ1 = r1/c1

і продовжений далі за формулами (3) послідовно при i=2,3,…,n, причому при i=n, ​​в силу dn=0, отримаємо δn=0.Отже, вважаючи (2) i=n, будемо мати

xn = λn = (rn – bn λn-1)/( cn – bn δn-1)

(де λn-1, δn-1 – вже відомі з попереднього кроку числа). Далі за формулами (2) послідовно перебувають xn-1 , xn-2 ,…, x1 при i=n-1, n-2,…,1 відповідно.

Таким чином, рішення рівнянь виду (1) описуємо способом, званим методом прогонки, зводиться до обчислень за трьома простими формулами: знаходження так званих прогонкових коефіцієнтів δi λi за формулами (3) при i=1,2,…,n (пряме прогонування ) і потім невідомих xi за формулою (2) при i=n-1, n-2,…,1 (зворотне прогін).

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

Будемо називати прогін коректним, якщо знаменники прогоночних коефіцієнтів (3) не звертаються в нуль, і стійкою, якщо |δi|<1 при всіх i€{1,2,...,n}.

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

Теорема

Нехай коефіцієнти bi і di рівняння (1) при i=2,3,…,n-1 відмінні від нуля та нехай

|ci|>|bi|+|di| i=1,2,…,n. (4)

Тоді прогін (3), (2) коректна і стійка (тобто сi+biδi-1≠0, |δi|<1).

Доказ. Скористаємося методом математичної індукції задля встановлення обох необхідних нерівностей одночасно.

При i=1, з (4), маємо:

|c1|>|d1|≥0

— нерівність нулю першої пари прогінних коефіцієнтів, а також

|δ1|=|- d1/ c1|<1

Припустимо, що знаменник (i-1)-x прогоночних коефіцієнтів не дорівнює нулю і що | i-1 | <1. Тоді, використовуючи властивості модулів, умови теореми та індукційні припущення, отримуємо:

|сi+biδi-1|≥|ci| — |biδi-1|>|bi|+|di| — |bi|*|δi-1|= |di|+|bi|(1 — | δi-1|)> |di|>0

а з урахуванням цього

|δi|=|- di/ сi+biδi-1|=|δi|/| сi+biδi-1|<|δi|/|δi|=1

Отже, сi+biδi-1 ≠0 і |δi|<1 за всіх i€{1,2,...,n }, тобто. має місце затверджена в умовах коректність і стійкість прогонки. Теорему доведено.

Нехай А – матриця коефіцієнтів даної системи (1), що задовольняють умовам теореми, та нехай

δ1= — d1/ c1 , δi=|- di/ ci+biδi-1 (i=2,3,…,n-1), δn=0

— прогінні коефіцієнти, що визначаються першою з формул (3), а

∆i= сi+biδi-1 (i=2,3,…,n)

— знаменники цих коефіцієнтів (відмінні від нуля згідно із затвердженням теореми). Безпосередньою перевіркою легко переконається, що має місце уявлення A=LU, де

c1 0 0 0 … 0 0 0

b2 ∆2 0 0 … 0 0 0

L= 0 b3 ∆3 0 … 0 0 0

0 0 0 0 … bn-1 ∆n-1 0

0 0 0 0 … 0 bn ∆n


1 -δ1 0 0 … 0 0 0

0 1 δ2 0 … 0 0 0

U = 0 0 1 δ3 … 0 0 0

0 0 0 0 … 0 1 -δn-1

0 0 0 0 … 0 0 1

Єдине затвердження теореми LU-розкладання матриць. Як бачимо, LU-розкладання тридіагональної матриці А може бути виконано дуже простим алгоритмом, що обчислює ∆i δi при зростаючих значеннях i. При необхідності попутно може бути розрахований

n

det A = c1 ∏ ∆i.

i=2

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

Список використаної літератури

  1. В.М. Вержбітський «Кількісні методи. Лінійна алгебра та нелінійні рівняння», Москава «Вища школа 2000».

© Реферат плюс



Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *