Линейных алгебраических уравнений ax=B, где

Вид материала

Решение

Содержание Метод Гаусса с выбором главного элемента по столбцу Прямой ход. Обратный ход Метод Холецкого Метод прогонки Обратный ход прогонки.

Подобный материал:

• В. Н. Страхов новая теория регуляризации систем линейных алгебраических уравнений, 25.89kb.
• Вопросы к экзамену 1 семестр, 56.89kb.
• Контрольная работа по линейной алгебре и аналитической геометрии «Системы линейных, 383.4kb.
• Лекция № Тема 1: Системы линейных алгебраических уравнений. Метод Гаусса решения систем, 50.61kb.
• Й в виде прямоугольной таблицы элементов кольца или поля, которая представляет собой, 71.89kb.
• Для решения систем линейных алгебраических уравнений с ленточной матрицей, с понятием, 89.58kb.
• Лабораторная работа, 155.79kb.
• Вопросы к экзамену по курсу «Высшая математика часть, 14.58kb.
• Решение систем линейных алгебраических уравнений методом прогонки, 112.31kb.
• Урок в 7 классе по теме: «Системы линейных уравнений в решении алгебраических задач», 97.42kb.

Практическое занятие №4


Решение систем линейных уравнений.

Прямые методы


Пусть рассматривается система линейных алгебраических уравнений AX=B, где

, , .


Метод решения задачи называют прямым, если он позволяет получить решение после выполнения конечного числа элементарных операций. К прямым методам решения относятся метод Гаусса и его модификации, метод Холецкого и метод прогонки.

Метод Гаусса с выбором главного элемента по столбцу

На k-ом шаге прямого хода в качестве ведущего элемента выбирают максимальный по модулю коэффициент среди коэффициентов при неизвестной в уравнениях с номерами i = k+1, ... , m.

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

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


Пример 1

Решение системы методом Гаусса с выбором главного элемента по столбцу.




Пусть Ax=b, где

A= , b=


Прямой ход.

1 шаг. Максимальный по модулю элемент 1-го столбца . Переставим 1-ое и 3-е уравнения местами:

A= , b=

Вычислим масштабирующие множители 1 шага:

       

и выполним преобразование матрицы и вектора:

A1=  b1=


2 шаг. Вычислим масштабирующие множители 2 шага:

    .

Второй шаг не изменяет матриц: A2=A1, b2= b1.

3 шаг. Максимальный по модулю элемент 3-го столбца . Переставим 3 и 4 уравнения местами.

A2= b2=

Вычислим масштабирующие множители 3 шага:



и выполним преобразование матрицы и вектора:

A3=  b3=


Обратный ход.

Из последнего уравнения находим: .

Из третьего уравнения системы находим .

Из второго уравнения находим .

Неизвестное находим из первого уравнения:

Ответ: .

Метод Холецкого

Если матрица системы является симметричной и положительно определенной, то для решения системы применяют метод Холецкого (метод квадратных корней). В основе метода лежит алгоритм специального LU-разложения матрицы A, в результате чего она приводится к виду A=. Если разложение получено, то как и в методе LU-разложения, решение системы сводится к последовательному решению двух систем с треугольными матрицами: и  . Для нахождения коэффициентов матрицы L неизвестные коэффициенты матрицы приравнивают соответствующим элементам матрицы A. Затем последовательно находят требуемые коэффициенты по формулам:

, i = 2, 3, ..., m,

, i = 3, 4, ..., m,

...............

     i = k+1, ... , m.




Пример 2

Решение системы методом Холецкого.

A= b=


Находим элементы матрицы L:

; ; ;

  ;  ;

.

 

Таким образом разложение матрицы A имеет вид:



Последовательно решаем системы и .

Решением 1-ой системы является вектор , а решение 2-ой системы вектор .

Ответ:    

Метод прогонки

Он является модификацией метода Гаусса для частного случая разряженных систем – системы уравнений с трехдиагональной матрицей, которые имеют следующий вид:



На главной диагонали матрицы этой системы стоят элементы b_i, над ней – элементы c_i, под ней – элементы a_i. При этом обычно все коэффициенты b_i не равны 0.

Метод прогонки состоит из 2 этапов – прямой прогонки и обратной. Прямая прогонка состоит в том, что каждое неизвестное x_i выражается через x_i+1 с помощью прогоночных коэффициентов α_i, β_i: .

Прямая прогонка. Выразим x₁ из первого уравнения: .

Преобразуем первое уравнение системы к виду , где ,

Подставим полученное выражение во второе уравнение системы и преобразуем его к виду : , и т.д.

На i-ом шаге уравнение преобразуется к виду , где , .

Обратная прогонка. На m-ом шаге подстановка в последнее уравнение выражения дает возможность определить значение :

.

Значения остальных неизвестных находятся по формулам: , i = m-1, m-2, ..., 1.

 

Пример 3

Решение системы методом прогонки.




Прямой ход прогонки.

Вычислим прогоночные коэффициенты:

1. Вычислим знаменатель ,
   

,

2. ,   
   
3. , ,
   

4. , ,
   

Обратный ход прогонки.

Находим значения неизвестных:

,

,

,




Ответ:       .


Задачи для самостоятельного решения:

Задача 1

Методом Гаусса с выбором главного элемента найти решение системы уравнений:


Задача 2

Найти     разложение матрицы:




Задача 3


Можно ли  применять метод Холецкого к системе уравнений, матрица которой  имеет вид:


Задача 4

Решите систему уравнений методом прогонки.

1. 
   
2.