Шукати в цьому блозі

понеділок, 15 лютого 2016 р.

Метод Гауса


Матеріал з Вікіпедії — вільної енциклопедії.
Ме́тод Га́уса — алгоритм розв'язку системи лінійних алгебраїчних рівнянь.
Початок алгоритму. \begin{cases} a_{11} \cdot x_1 + a_{12} \cdot x_2 + ... + a_{1n} \cdot x_n = b_1 & I \\ a_{21} \cdot x_1 + a_{22} \cdot x_2 + ... + a_{2n} \cdot x_n = b_2 & II \\ ... & ... \\ a_{m1} \cdot x_1 + a_{m2} \cdot x_2 + ... + a_{mn} \cdot x_n = b_m & M \end{cases}
Прямий хід: Шляхом елементарних перетворень рядків (додавань до рядка іншого рядка, помноженого на число, і перестановок рядків) матриця приводиться до верхньотрикутного вигляду(ступінчатого вигляду).
З цього моменту починається зворотний хід.
З останнього ненульового рівняння виражаємо кожну з базисних змінних через небазисні і підставляємо в попередні рівняння. Повторюючи цю процедуру для всіх базисних змінних, отримуємо фундаментальний розв'язок.

Приклад

\left\{\begin{array}{ccc} 2x + y - z &=& 8 \\ -3x - y + 2z &=& -11 \\ -2x + y + 2z &=& -3 \end{array}\right.
Запишемо розширену матрицю системи
\left[\begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{array}\right]

Допустимі операції для кожного рядка

  • перестановка рядків;
  • множення та ділення на число (окрім нуля);
  • додавання та віднімання іншого рядка (можливо помноженого чи поділеного на число).
Мета цих дій — звести квадратну матрицю, в цьому прикладі розміру 3х3, (розташована зліва від вертикальної лінії) до одиничної матриці. Тоді стовпчик справа від лінії і буде розв'язком системи рівнянь.

Алгоритм прямого ходу

Перебираємо стовпчики матриці і здійснюємо рядкові операції, щоб у кожному стовпчику:
  • діагональний елемент став рівним одиниці;
  • елементи під діагональним стали рівними нулю.
Ділимо перший рядок на 2, щоб отримати 1 як перший діагональний елемент:
\left[\begin{array}{ccc|c} 1 & 1/2 & -1/2 & 4 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{array}\right]
Додаємо до другого рядка перший, помножений на 3, щоб отримати піддіагональний елемент 0:
\left[\begin{array}{ccc|c} 1 & 1/2 & -1/2 & 4 \\ 0 & 1/2 & 1/2 & 1 \\ -2 & 1 & 2 & -3 \end{array}\right]
Додаємо до третього рядка перший, помножений на 2, щоб отримати другий піддіагональний елемент 0:
\left[\begin{array}{ccc|c} 1 & 1/2 & -1/2 & 4 \\ 0 & 1/2 & 1/2 & 1 \\ 0 & 2 & 1 & 5 \end{array}\right]
Переходимо до наступного стовпчика. Множимо другий рядок на 2, щоб отримати другий діагональний елемент 1:
\left[\begin{array}{ccc|c} 1 & 1/2 & -1/2 & 4 \\ 0 & 1 & 1 & 2 \\ 0 & 2 & 1 & 5 \end{array}\right]
Віднімаємо від третього рядка другий, помножений на 2, щоб отримати піддіагональний елемент 0:
\left[\begin{array}{ccc|c} 1 & 1/2 & -1/2 & 4 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & -1 & 1 \end{array}\right]
Переходимо до наступного стовпчика. Множимо останній рядок на −1, щоб отримати третій діагональний елемент 1:
\left[\begin{array}{ccc|c} 1 & 1/2 & -1/2 & 4 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & 1 & -1 \end{array}\right]

Алгоритм зворотного ходу

Перебираємо стовпчики матриці у зворотному порядку і здійснюємо рядкові операції, щоб у кожному стовпчику елементи над діагональним стали рівними нулю.
Віднімаємо від другого рядка третій, щоб отримати наддіагональний елемент 0:
\left[\begin{array}{ccc|c} 1 & 1/2 & -1/2 & 4 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & -1 \end{array}\right]
Додаємо до першого рядка третій, поділений на 2, щоб отримати другий наддіагональний елемент 0:
\left[\begin{array}{ccc|c} 1 & 1/2 & 0 & 7/2 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & -1 \end{array}\right]
Переходимо до наступного стовпчика. Віднімаємо від першого рядка другий, поділений на 2, щоб отримати наддіагональний елемент 0:
\left[\begin{array}{ccc|c} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & -1 \end{array}\right]
Опубліковано о
Мітки:

Немає коментарів:

Дописати коментар

Примітка: лише член цього блогу може опублікувати коментар.

Підписатися на: Дописати коментарі (Atom)