Метод lu – розкладу (метод розкладу на трикутні матриці або метод lu – факторизації ) icon

Метод lu – розкладу (метод розкладу на трикутні матриці або метод lu – факторизації )



НазваниеМетод lu – розкладу (метод розкладу на трикутні матриці або метод lu – факторизації )
Дата конвертации22.09.2012
Размер43.02 Kb.
ТипДокументы

Метод LU – розкладу

(метод розкладу на трикутні матриці або метод LU – факторизації )


Алгоритми цього методу досить близькі до методу Гауса. Основна перевага методу LU – факторизації в порівнянні з методом Гауса є можливість більш простого одержання розв’язку для різних векторів b системи лінійних алгебраїчних рівнянь

A · x = b (1)

A – матриця розміру nn із сталими коефіцієнтами;

bn-мірний вектор вільних членів;

х n-мірний вектор невідомих.

Матриця системи А представляється у вигляді добутку двох трикутних матриць L та U

А =L · U, де

,

^ L – нижня трикутна матриця, U – верхня трикутна матриця.

Зауважимо, що на головній діагоналі матриці U стоять одиниці. Це в свою чергу означає, що визначник матриці А дорівнює добутку діагональних елементів lii матриці L. (det U = 1; det L = l11l22…lnn; det A = det L).

Отже, систему (1) можна записати у вигляді

L · U · x = b. (2)

Введемо допоміжний вектор у як

U · x = у (3)
^

Тоді можна записати, що


L · у = b. (4)

Розв’язування системи (1) або (2) відбувається в два етапи: спочатку розв’язується система L · у = b, а потім U · x = у.

Така послідовність розв’язку дає перевагу методу (в порівнянні з методом Гауса) – якщо потрібно розв’язати декілька систем з однією і тією ж матрицею А, задача суттєво спрощується, оскільки зберігаються матриці L та U.

Розв’язок системи L · у = b називається прямим ходом, а системи U · x = у – оберненим ходом.

Розглянемо прямий хід.Завдяки спеціальній формі матриці L вектор у можна легко визначити. Для цього (4) перепишемо у вигляді системи рівнянь




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

(5)

gif" name="object6" align=absmiddle width=152 height=45> для

При оберненому ході вектор х визначається з системи рівнянь (3)

x1 + u12x2 + u13x3 + … + u1nxn = y1

x2 + u23x3 + … + u2nxn = y2

x3 + … + u3nxn = y3

………………………………

xn = yn

Починаючи з останнього рівняння, можна послідовно знайти компоненти вектора х. В загальному вигляді вони визначаються за формулами

для (6)

Тепер розглянемо LU – розклад матриці А.

Елементи матриці L та U визначаються за наступними формулами:

де , де ()

, де ()

, де ().

Ці ж самі формули можна записати у більш зручному вигляді (метод Краута).

У варіанті методу, що називається методом Краута, використовується наступна послідовність знаходження елементів матриць L та U () – де k – крок.

Для всіх

де (7)

де (8)

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

Крім того, .

Тобто, при k =1

для всіх

для всіх .



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




Алгоритм

1) k =1


Обчислюємо

для всіх

для всіх .

2) k = k + 1


де

де .

Продовжуємо до тих пір, доки k = n.

Зауваження щодо алгоритму побудови програми:

  1. Необхідні в цих співвідношеннях значення елементів матриць L та U обчислюються на попередніх етапах процесу.

  2. Кожний елемент aij матриці А потрібен тільки для обчислення відповідних елементів матриці L та U ( тобто, в подальшому процесі aij не потрібні). Оскільки нульові елементи матриць L та U, а також одиничну діагональ матриці U запам’ятовувати не потрібно, тобто в процесі обчислення матриці L та U можуть бути записані на місце матриці А. Причому матриця L розташована в нижньому трикутнику (i ≥ j), U – відповідно в верхньому трикутнику (i < j) матриці А.

  3. Розклад матриці А на матриці L та U , як правило, об’єднують з прямим ходом. Може бути використана наступна послідовність обчислень: спочатку обчислюється перший стовпець матриці L , потім перший рядок матриці U та перший елемент вектора у; далі – другий стовпець матриці L , другий рядок матриці U та другий елемент вектора у і т.д.



Матрицю А можна розкласти на дві трикутні матриці L та U при умові, що головні діагональні мінори матриці А відмінні від нуля. Якщо ця умова не виконується, наприклад, для k-го головного діагонального мінора, то при обчисленні елемента lkk матриці L за формулою (7) він стане рівним нулю. Це в свою чергу призведе до неможливості обчислення елементів ukj матриці U (ділення на нуль). Усунути таку ситуацію можна було б шляхом перевірки умов нерівності нуля головних діагональних мінорів до розкладу А = L U . Однак така перевірка пов’язана із значними затратами машинного часу, що перевищує затрати часу пов’язані із розкладом А = L U (крім того перевірка – це обчислення тих самих визначників).

Тому доцільніше проводити перевірку умови lkk = 0 безпосередньо в процесі обчислення елементів lij та uij. Тоді при виконанні цієї умови потрібно переставляти відповідний k-й рядок матриці А з наступними k + s рядками (), до тих пір, доки не виконається умова








Похожие:

Метод lu – розкладу (метод розкладу на трикутні матриці або метод lu – факторизації ) iconТема: «счастье это когда тебя понимают»: так ли это?
Основные методы и приемы: метод наблюдения, словесный метод, игровой метод, метод «вопроса в связи с обстоятельствами»
Метод lu – розкладу (метод розкладу на трикутні матриці або метод lu – факторизації ) iconРеферат з математики
Одним з найпоширеніших методів розв'язування систем лінійних рівнянь є метод послідовного виключення невідомих, або метод Гаус­са....
Метод lu – розкладу (метод розкладу на трикутні матриці або метод lu – факторизації ) iconПрибыль и ее роль в рыночной экономике Содержание
Метод прямого счета, аналитический метод и метод совмещенного расчета
Метод lu – розкладу (метод розкладу на трикутні матриці або метод lu – факторизації ) iconПрограмма составлена кандидатом физ мат наук В. А. Зайцевым
Автоколебания. Метод точечных преобразований. Системы с переменной структурой. Приближенное исследование автоколебаний. Метод эквивалентной...
Метод lu – розкладу (метод розкладу на трикутні матриці або метод lu – факторизації ) iconФедеральное агентство по образованию Государственное образовательное учреждение
Вычислить определитель 3-го порядка, используя метод Саррюса (или метод треугольников) и метод разложения по минорам какого-нибудь...
Метод lu – розкладу (метод розкладу на трикутні матриці або метод lu – факторизації ) iconЗвіт до лабораторної роботи №3 з курсу “Комп’ютерні методи дослідження інформаційних процесів та систем” на тему
До ітераційних методів належать: метод простої ітерації, метод Зейделя, метод верхньої релаксації та інші
Метод lu – розкладу (метод розкладу на трикутні матриці або метод lu – факторизації ) icon6 Метод Рунге-Кутта 2-ого порядка (модифицированный метод Эйлера)
В правой части полагаем, как в исходном методе Эйлера. Получаем явный метод, для которого погрешность
Метод lu – розкладу (метод розкладу на трикутні матриці або метод lu – факторизації ) iconЧто такое метод проектов
Метод проектов (от греческого путь исследования). Метод проектов это модель обучения, которая вовлекает ученика в процесс решения...
Метод lu – розкладу (метод розкладу на трикутні матриці або метод lu – факторизації ) iconМетоды беседы в психологии. Метод беседы
Метод беседы — психологический вербально-коммуникативный метод, заключающийся в ведении тематически направленного диалога между психологом...
Метод lu – розкладу (метод розкладу на трикутні матриці або метод lu – факторизації ) iconМетод прогону
Більшість технічних задач зводиться до розв’язування систем лар, в яких матриці містять багато нульових елементів, а ненульові елементи...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©rushkolnik.ru 2000-2015
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы