Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


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



 

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

 

a11 x 1 + a12 x 2 + a13 x 3 +... + a1n x n = b 1

a21 x 1 + a 22 x 2 + a23 x 3 +... + a2n x n = b 2 (4.1)

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

an1 x 1 + an2 x 2 + an3 x 3 +... + ann x n = b n

 

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

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

 

Совокупность чисел x 1 = λ 1, x 2 = λ 2, ..., 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

k1 = -2, k2 = 2, k1 ≠ k2, т.е. прямые пересекаются

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

k1 =1, k2 = 1, k1 = k2, т.е. прямые не пересекаются

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

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

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

 

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

det A = - 0, 0001 ≠ 0

точное решение x1 = 1, x2 = 1

 

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

x1 = 3, x2 = -1, 0203.

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

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

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

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

 

, всегда ≥ 1.

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

 

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

 

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

 

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

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

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

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

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

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

 

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

 

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

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

 

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

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

, , ..., ,

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

Метод Гаусса

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

 

,

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

 

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

2. Находим неизвестные, начиная с xn, xn-1, xn-2,..., x2, x1.

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

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

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

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

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

; (4.4)

 

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

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

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

 

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

, (4.5)

тогда

(4.6)

 

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

 

.

Выразим (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) определим xn, затем

,

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

 

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

(4.10)

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

 

Тема 5


Поделиться:



Популярное:

Последнее изменение этой страницы: 2016-03-15; Просмотров: 1434; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.044 с.)
Главная | Случайная страница | Обратная связь