Решение систем линейных алгебраических уравнений

 

Рассмотрим систему, состоящую из n уравнений с n неизвестными.

 

a₁₁ x ₁ + a₁₂ x ₂ + a₁₃ x ₃ +... + a_1n x _n = b ₁

a₂₁ x ₁ + a ₂₂ x ₂ + a₂₃ x ₃ +... + a_2n x _n = b ₂ (4.1)

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

a_n1 x ₁ + a_n2 x ₂ + a_n3 x ₃ +... + a_nn x _n = b _n

 

где x _i – неизвестные, подлежащие определению, a_ij – коэф-фициенты при неизвестных; b _i - числа, называемые свободными членами (правыми частями) системы уравнений.

Форма записи системы (4.1) - скалярная

 

Совокупность чисел x ₁ = λ ₁, x ₂ = λ ₂, ..., x _n = λ _n, удовлетворяющих (4.1) называется решением СЛАУ.

СЛАУ называется совместной, если она имеет хотя бы одно решение; в противном случае она называется несовместной.

СЛАУ называется определенной, если это решение - единственное.

Если СЛАУ не имеет ни одного решения, то такая система является неопределенной.

Задача теории систем линейных уравнений состоит в разработке методов, позволяющих узнать:

- совместна ли данная СЛАУ;

- если совместна, то установить число решений;

- указать способ отыскания этих решений.

 

Матричная форма записи системы (4.1) имеет вид

А = ; x = ; b = ; (4.2)

Некоторые обозначения:

А^Т – матрица, транспонированная к матрице А, т.е. a _ij = a _ji.

А^-1 – матрица, обратная к матрице А, т.е. А^-1 · А = I,

где I - единичная матрица.

 

При решении СЛАУ возникают проблемы, связанные с вопросами:

1) разрешима ли данная СЛАУ;

2) каким методом ее решать;

3) какова чувствительность решения к ошибкам округления исходных данных.

 

Рассмотрим эти вопросы подробнее.

1) Теорема (из курса высшей алгебры)

Система n уравнений с n неизвестными, определитель которой отличен от 0, имеет решение, причем единственное.

(Это условие необходимое, но не достаточное.)

Покажем разрешимость СЛАУ на графике для системы двух уравнений.

det A = 2∙ 1 – (-2)∙ 1 = 4 ≠ 0

k₁ = -2, k₂ = 2, k₁ ≠ k₂, т.е. прямые пересекаются

det A = (-1)∙ (-1) – 1∙ 1 = 0

k₁ =1, k₂ = 1, k₁ = k₂, т.е. прямые не пересекаются

2) К выбору методов решения необходимо подходить рационально: например, метод Крамера требует около n²n! операций умножения и деления.

Т.е. для системы с 20 уравнениями и 20 неизвестными это число составляет 10²¹. Для современных ЭВМ, выполняющих миллионы операций в сек., для решения такой системы потребуется около 10¹⁵ сек. или 3∙ 10⁶ лет.

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

 

3) Устойчивость решения относительно погрешностей правых частей и элементов матрицы покажем на примере:

det A = - 0, 0001 ≠ 0

точное решение x₁ = 1, x₂ = 1

 

Если правые части вычислены с незначительной погрешностью, b₁ = 1, 989903 и b₂ = 1, 970106, то получим решение

x₁ = 3, x₂ = -1, 0203.

Такие СЛАУ являются плохо обусловленными.

Геометрическая иллюстрация:

Графики прямых этой плохо обусловленной системы почти параллельны. Следовательно, небольшое изменение наклона или сдвиг одной прямой значительно влияет на положение точки пересечения прямых.

Критерий плохой обусловленности

 

, всегда ≥ 1.

Чем больше , тем хуже обусловлена система ( ≈ 10³ – 10⁴).

 

На практике обычно проверяют неравенство 0 определителя СЛАУ.

 

Методы решения СЛАУ

 

Методы решения СЛАУ подразделяются на точные и итерационные.

Точные – это методы, которые определяют решение при помощи конечного числа арифметических операций.

При этом, если исходные данные и вычисления точны, то получается точное решение (методы Крамера, Гаусса).

Точные методы выполняются в два этапа:

- преобразование исходной СЛАУ к более простому виду;

- решение упрощенной системы и получение неизвестных.

 

Приближенные (итерационные) методы

 

Предварительно задаются некоторыми приближенными значениями неизвестных , ..., . Из этих значений тем или иным способом получают новые ‘’улучшенные’’ приближенные значения , ..., . С новыми значениями поступают также.

При выполнении определенных условий после бесконечного числа шагов можно получить точное решение.

 

На практике вычисления прерывают при достижении заданной точности ε. Для этого на каждой итерации с заданной точностью сравнивают два последовательных приближения

Если выполняются условия

, , ..., ,

то полученные на i - итерации значения , ..., считаются решением СЛАУ.

Метод Гаусса

(последовательного приближения неизвестных)

 

,

где А = ; x = ; b = ;

 

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

2. Находим неизвестные, начиная с x_n, x_n-1, x_n-2,..., x₂, x₁.

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

(модификация метода Гаусса для систем

с 3-х диагональной матрицей коэффициентов)

, i= 1, 2, ..., n, (4.3)

Каждое i – уравнение содержит не более 3 неизвестных x_i-1, x_i, x_i+1.

; (4.4)

 

Последовательные исключения выполняются так:

Из ''0'' уравнения выражаем и подставляем в 1-е уравнение .

Затем выразим x₁ через x₂ и подставим во 2-е уравнение и т.д.

 

Будем считать, что соотношение между x_i и x_i+1 известно

, (4.5)

тогда

(4.6)

 

Подставим (4.6) в i – уравнение и решим относительно x_i.

 

.

Выразим (4.7)

Сравнив (4.7) и (4.5), получим прогоночные коэффициенты

, (4.8)

При i = 0 из (4.5) получим .

сравнив с (4.4) получим

, (4.9)

Этапы метода прогонки

 

1) Прямой ход: каждое i – неизвестное выражается через i+1– е с помощью прогоночных коэффициентов (4.8) и (4.9) (i =0, 1, ..., n-1)

2) Обратный ход: с помощью (4.5) определим x_n, затем

,

и сравним с последним уравнением (4.3).

 

Выразив x_n, получим

(4.10)

Далее, используя (4.5) и формулы прогоночных коэффициентов (4.8) и (4.9), находят x_n-1, x_n-2,..., x₁, x₀.

 

Тема 5

⇐ Предыдущая123456Следующая ⇒

Поделиться:

Популярное:

1. D. СОЦИОИДЕОЛОГИЧЕСКАЯ СИСТЕМА ВЕЩЕЙ И ПОТРЕБЛЕНИЯ
2. F. ЦИФРОВЫЕ СИСТЕМЫ РАСПРОСТРАНЕНИЯ
3. I. Местное самоуправление в системе институтов конституционного строя. История местного самоуправления
4. I. Методические принципы физического воспитания (сознательность, активность, наглядность, доступность, систематичность)
5. II. Проверка и устранение затираний подвижной системы РМ.
6. II.2. Локальные геосистемы – морфологические единицы ландшафта
7. III 7 Взаимодействие аллельных и неаллельных генов с решением
8. III. Борьба за разрешение восточного вопроса.
9. III.3. Композиционное и пространственное решение пейзажей
10. III.3. Система классификационных единиц
11. IV. Падение отработочной системы.
12. IV. СООТНОШЕНИЕ СИМВОЛИЧЕСКИХ И ЕСТЕСТВЕННО-ЯЗЫКОВщХ СИСТЕМ КАК ФАКТОР, ОПРЕДЕЛЯЮЩИЙ ХАРАКТЕР КУЛЬТУРЫ