Xreferat.com » Рефераты по математике » Численные методы

Численные методы

наступна теорема, яку сформулюємо без доведення.

ТЕОРЕМА: Нехай система (2) має єдиний розв’язок. Послідовні наближення (3) збігаються до розв’язку системи (2) за довільного початкового наближення тоді та й тільки тоді, коли усі власні значення матриці за модулем менше одиниці.

Повернемось зараз до способів приведення (1) до форми (2). Запишемо (1) у розгорнутій формі

Якщо для усіх , то можна (7) зобразити у вигляді

Звідси два найпростіших ітераційних метода.

Метод Якобі, який задається рекурентним співвідношенням:

Метод Зейделя, де вже знайдені компоненти беруться у правій частині співвідношення з (n+1)-го наближення, а інші- з n-го наближення:

Можна дати матричну форму методів Якобі і Зейделя.

Нехай матрицю А наведено у вигляді:

де -нижня трикутна матриця з нульовою головною діагонал-лю;

D - діагональна матриця з на головній діагоналі;

-верхня трикутна матриця з нульовою головною діагоналлю.

За припущенням існує

Тоді зображенню у формі (8) відповідає

або

Таким чином, методу Якобі відповідає ітераційна процедура

Методу Зейделя відповідає

Використовуючи сформульовані раніш достатні умови збіжності , самостійно переконайтесь, що достатніми умовами збіжності методу Якобі є

або

тобто діагональне переваження матриці А.

Можна довести, що за вказаних умов збігається і метод Зейделя.

Покажемо, що до форми (2), що задовольняє умовам збіжності, може бути зведена довільна система (1) з

Дійсно,візьмемо матрицю де -матриця з достатньо малими за модулем елементами. Множачи (1) зліва на С маємо

тобто одержали форму (2) з

За рахунок вибору достатньо малих можна задовольнити умовам збіжності.

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


ІТЕРАЦІЙНІ МЕТОДИ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ


АЛГЕБРАЇЧНИХ РІВНЯНЬ.


Розглядається система лінійних алгебраїчних рівнянь

(1)

де - квадратна матриця вимірності

- вектор - стовпець правих частин системи;

- вектор - стовпець невідомих.

Ідея найпростіших ітераційних методів розв’язання системи (1) полягає у наступному. За допомогою еквівалентних перетворень система (1) зводиться до системи вигляду

(2)

де -квадратна матріця

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

А потім задається деяке початкове наближення (наприклад, у якості береться вектор , або деякий розв’язок системи (1), який одержується іншим методом з деякою похибкою). Інші наближення послідовно знаходяться за рекурентною формулою

(3)

доки на деякому кроці не буде досягнута задана точність

обчислення значення невідомого вектору .

Виникає питання, за яких умов на послідовність

збігається (у певному розумінні) до точного розв’язку .

Не зупиняючись на подробицях (дивись спецкурс ‘Додаткові розділи чисельного аналізу’), дамо деякі достатні умови, за яких

або

або

Швидкість збіжності оцінюється нерівністю

де - відстань між векторами та , що може бути заданою:

коли виконується умова (4);

коли виконується умова (5);

коли виконується умова (6).

Задаючи потрібну точність можна з рівності

одержати необхідну кількість ітерацій , щоб досягти задане .

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

ТЕОРЕМА: Нехай система (2) має єдиний розв’язок. Послідовні наближення (3) збігаються до розв’язку системи (2) за довільного початкового наближення тоді та й тільки тоді, коли усі власні значення матриці за модулем менше одиниці.

Повернемось зараз до способів приведення (1) до форми (2). Запишемо (1) у розгорнутій формі

Якщо для усіх , то можна (7) зобразити у вигляді

Звідси два найпростіших ітераційних метода.

Метод Якобі, який задається рекурентним співвідношенням:

Метод Зейделя, де вже знайдені компоненти беруться у правій частині співвідношення з (n+1)-го наближення, а інші- з n-го наближення:

Можна дати матричну форму методів Якобі і Зейделя.

Нехай матрицю А наведено у вигляді:

де -нижня трикутна матриця з нульовою головною діагоналлю;

D - діагональна матриця з на головній діагоналі;

-верхня трикутна матриця з нульовою головною діагоналлю.

За припущенням існує

Тоді зображенню у формі (8) відповідає

або

Таким чином, методу Якобі відповідає ітераційна процедура

Методу Зейделя відповідає

Використовуючи сформульовані раніш достатні умови збіжності , самостійно переконайтесь, що достатніми умовами збіжності методу Якобі є

або

тобто діагональне переваження матриці А.

Можна довести, що за вказаних умов збігається і метод Зейделя.

Покажемо, що до форми (2), що задовольняє умовам збіжності, може бути зведена довільна система (1) з

Дійсно,візьмемо матрицю де -матриця з достатньо малими за модулем елементами. Множачи (1) зліва на С маємо

тобто одержали форму (2) з

За рахунок вибору достатньо малих можна задовольнити умовам збіжності.

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


МЕТОД ПРОГОНКИ.


Система уравнений для определения коэффициентов сплайна представляет собой частный случай систем линейных алгебраических уравнений

с трехдиагональной матрицей , т.е. с матрицей, все элементы которой,не лежащие на главной и двух побочных диагоналях, равны нулю при та

В общем случае системы линейных алгебраических уравнений с трехдиагональной матрицей имеют вид

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

Т.е. матрицу А можно записать

  1. Идея метода прогонки состоит в следующем. Решение системы (1) ищется в виде

где -неизвестные коэффициенты, которые последовательно находятся от до (прямая прогонка ), а затем последовательно вычисляются (обратная прогонка) .

Выведем формулы для вычисления Из (3) можно получить

Подставляя имеющиеся выражения для в уравнение (1),приходим при к уравнению Последнее уравнение будет выполнено если коэффициенты выбрать такими, чтобы выражения в квадратных скобках обращались в нуль.

А именно, достаточно положить Для отыскания всех достаточно задать

Эти начальные значения находим из требования эквивалентности условия (3) при т.е. условия , первому из уравнений (2).

Таким образом, получаем

(5)

Нахождение коэффициентов по формулам (4), (5) называется прямой прогонкой. После того, как прогоночные коэффициенты найдены, решение системи (1), (2) находится по рекуррентной формуле (3), начиная с Для начала счета по этой формуле требуется знать , которое определяется из уравнений

И равно

.

Нахождение по формулам

(6)

называется обратной прогонкой. Алгоритм решения системы (1), (2) определяемый формулами (4)-(6) называется методом прогонки.

Метод прогонки можно пременять, если знаменатели выражений (4), (6) не

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: