- •Система линейных алгебраических уравнений (СЛАУ).
- •Совокупность неизвестных x j, j 1,2,3,..., m
- •Классификация СЛАУ
- •Методы решения СЛАУ
- •Первый этап (прямой ход) заключается в последовательном исключении неизвестных из системы уравнений и
- •Пример. Решить СЛАУ методом Гаусса.
- •Второй этап. Вычисляем неизвестные
- •Для уменьшения погрешности вычислений используют модификации метода Гаусса, которые определяются выбора«ведущего» элемента. В
- •Обусловленность систем линейных алгебраических уравнений.
- •Метод простых итераций Алгоритм метода состоит из трёх этапов.
- •где вектор d – приведенный столбец свободных членов,матрица
- •Пример. Решить СЛАУ методом Гаусса 1.000
Система линейных алгебраических уравнений (СЛАУ).
В общем виде СЛАУ можно записать в следующем виде
|
a11x1 a12x2 ....... |
a1m xm b1 |
|
. |
a21x1 |
a22x2 ....... |
a2m xm b2 |
|
.......... ....... ........... .... |
||
|
......... |
||
|
an1x1 |
an2x2 ....... |
anmxm bn |
Совокупность коэффициентовaij , i =1,2,3,…,n; j=1,2,3,….,m системы
можно представить в виде матрицы:
A A
a11
a21
an1
a12 |
a13 |
|
|
a1m |
|
a22 |
a23 |
|
|
a2m |
|
|
|||||
|
|
|
|
||
an2 |
an3 |
|
|
|
|
anm |
1
Совокупность неизвестных x j, j 1,2,3,..., m
Совокупность неизвестных bi , i 1,2,3,..., n
|
|
x1 |
|
|
|
|
|
- в виде вектора |
x x2 |
|
|
|
|
... |
|
|
|
|
|
|
|
xm |
|
|
|
b1 |
|
|
|
|
|
- в виде вектора |
b b2 |
|
|
|
|
... |
|
|
|
|
|
|
|
bn |
|
Используя выше приведенные определения, запишем СЛАУ в матричном виде:
|
|
|
|
|
|
|
A x b |
|
|
|
|
|
|
|
|
|
x*1 |
|
||
|
|
|
* |
|
|
|
Решить СЛАУ значить найти такие значения вектора x |
* |
x |
|
2 |
|
|
|
... |
|
||||
|
|
|
|
|
|
|
|
|
|
x*m |
подстановка которого в систему, обращает каждое уравнение этой системы в тождество.
2
Классификация СЛАУ
СЛАУ называется:
1.Переобусловленной, если n>m
2.Недообусловленой, если n<m
3.Нормальной, если n=m
4.Однородной, если вектор b 0
5.Неоднородной, если вектор b 0
6.Если система, имеет хотя бы одно решение, она называется совместной. Система, не имеющая решений, называется несовместной.
7.Совместная система, имеющая единственное решение, называется определенной, а имеющая бесчисленное множество решений, называется неопределенной.
Очевидно, что однородная система всегда совместна, так как имеет хотя бы одно
решение x 0 , которое называется тривиальным.
3
Методы решения СЛАУ
Все методы решения СЛАУ можно разделить на две группы: точные и итерационные.
Точные методы позволяют получить решение путем выполнения определённого и точного количества арифметических операций. При этом погрешность решения определяется лишь точностью представления исходных данных и точностью вычислительных операций.
Итерационные методы дают некоторую последовательность приближений к решению. Пределом этой последовательности является решение системы уравнений. Решение, возможно, определить лишь с некоторой, как правило, заданной степенью точности . Количество итераций для достижения требуемой точности решения определяется величиной , выбором начального приближения и видом системы уравнений.
Точные методы
Метод обратной матрицы
|
|
1 |
|
1 |
|
|
1 |
|
|
1 |
|
|
|
|
|
||||||||
A x b |
A A x A |
b |
E x A |
b |
x* A |
b |
Метод Гаусса
Метод Гаусса включает два этапа.
4
Первый этап (прямой ход) заключается в последовательном исключении неизвестных из системы уравнений и состоит из n–1 шага. На первом шаге с помощью первого уравнения исключается x1 из всех последующих уравнений начиная со второго, на
втором шаге с помощью второго уравнения исключается x2 из последующих уравнений начиная с третьего и т.д. Последним исключается xn-1 из последнего n-го уравнения так, что последнее уравнение будет содержать только одно неизвестное xn. Такое
последовательное исключение неизвестных равносильно приведению матрицы коэффициентов к треугольному виду. Строка, с помощью которой исключаются неизвестные, называется ведущей строкой, а диагональный элемент в этой строке – ведущим элементом.
Второй этап (обратный ход) заключается в последовательном вычислении искомых неизвестных и состоит из n шагов. Решая последнее уравнение, находим неизвестное xn. Далее используя это значение из предыдущего уравнения
вычисляем неизвестное xn-1 и т.д. Последним найдем неизвестное x1 из первого уравнения.
|
|
|
|
|
|
Матрица, содержащая помимо. коэффициентов при |
неизвестных A |
||||
|
|
|
|
|
|
|
|||||
столбец свободных членов b , называется расширенной |
|
||||
C |
A |
|
b |
||
|
|
|
|
|
|
5
|
|
|
|
|
|
|
|
|
|
|
|
Алгоритм. |
|
||||
1. Строим расширенную матрицу С размерностью n на n+1, приписав, справа к матрицы |
A |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
вектор |
b |
|
|
|
|
|
|
|||||||||
|
С A |
b |
т.е. ci,j=ai,j , ci,n+1=bi , где i=1,2,3,…,n j=1,2,3,…,n |
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
c |
c |
|
c |
|
.... |
c |
|
c |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
11 |
12 |
|
13 |
|
1n |
|
1,n 1 |
|
|
|
|
|
|
|
|
|
|
c21 |
c22 |
|
c23 |
.... |
c2n |
|
c2,n 1 |
. Задаем номер ведущей строки k = 1 |
|
||
|
|
|
|||||||||||||||
|
|
|
|
c31 |
c32 |
|
c33 |
|
c3n |
|
c3,n 1 |
|
|
||||
С |
A |
|
b |
|
.... |
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
... |
|
|
|
|
|
|
|
|
|
.... .... .... |
.... |
.... |
|
|
|
|
|||||
|
|
|
|
|
|
|
cn2 |
|
cn3 |
.... |
cnn |
|
|
|
|
|
|
|
|
|
|
|
|
cn1 |
|
|
cn,n 1 |
|
|
2.Преобразуем все строки, расположенные ниже k-ой так, чтобы элементы cik=0,
для этого вычисляем множитель =-сi,k/ck,k и каждую i-ую строку заменяем суммой i–ой и
k-ой умноженной на , т.е. ci,j=ci,j+ *ck,j |
где i = k+1,k+2,k+3,….,n и j = k,k+1,k+2,…,n+1 |
3. Проверяем k = n-1 если нет, то выбираем новую ведущую строку k=k+1 и переходим на пункт 2, иначе выполняем пункт 4.
4. Обратный ход. Из последнего n-ого уравнения определяем последнее n-ое неизвестное. xn=cn,n+1/cn,n Последовательно, из предыдущих уравнений начиная с i=n-1,
вычисляем соответствующие неизвестные xi. Последним, определяется первое
неизвестное из первого уравнение. |
n |
||
|
|
||
|
(ci,n 1 |
ci, j * x j ) |
|
xi |
|
j i 1 |
|
|
|
6 |
|
|
|
||
|
|
ci,i |
Пример. Решить СЛАУ методом Гаусса.
4.00 |
1.00 |
1.00 |
x1 |
|
6.00 |
|||||
|
2.00 |
5.50 |
1.00 |
|
|
|
|
|
8.50 |
|
|
|
x |
2 |
|
|
|
||||
|
|
|
|
|
|
|||||
|
2.00 |
1.00 |
4.00 |
x3 |
|
7.00 |
Первый этап. Строим расширенную матрицу и преобразуем её к ступенчатому виду.
|
4.00 |
1.00 |
1.00 |
6.00 |
|
2.00 |
5.50 |
1.00 |
|
|
8.50 k=1 |
2.00 1.00 4.00 7.00
4.00 1.00 1.00 6.00
0.00 5.00 0.50 5.50 k=2
0.00 0.50 3.50 4.00
4.00 1.00 1.00 6.000.00 5.00 0.50 5.50
0.00 0.00 3.45 3.45
i=2 – складываем 2ую строку с 1ой умноженной на =-c21/c11=-2/4=-0.5
i=3 – складываем 3ую строку с 1ой умноженной на =-c31/c11=-2/4=-0.5
i=3 – складываем 3ую строку с 2ой умноженной на =-c32/c22=-0.5/5=-0.1
7
Второй этап. Вычисляем неизвестные
x3 |
|
3.45 |
1.00 |
|
|
|
|
|
|||
|
3.45 |
|
|
|
|
x2 |
(5.50 (0.50 1.00)) |
1.00 |
|
||
|
|
|
5.00 |
|
|
x1 |
(6.00 (1.00 1.00 1.00 1.00)) |
1.00 |
|||
|
|
|
4.00 |
|
|
|
1.00 |
|
|
||
|
|
|
|
|
|
x 1.00 |
|
|
|||
|
|
|
|
|
|
|
1.00 |
|
|
8
Для уменьшения погрешности вычислений используют модификации метода Гаусса, которые определяются выбора«ведущего» элемента. В модификации с частичным выбором на каждом k-м шаге прямого хода в качестве «ведущего» выбирается наибольший по модулю элемент из неприведённой части k-го столбца матрицы, т.е.
ckk max cik , i k,k 1,k 2,...,n
i
Строка, содержащая этот элемент, переставляется с k-й строкой расширенной матрицы.
При полном выборе в качестве «ведущего» элемента выбирается максимальный по модулю элемент из всей неприведённой части матрицы коэффициентов системы:
ckk max cij , i, j k,k 1,k 2,..., n
i, j
Для этого осуществляется необходимая перестановка как строк, так и столбцов в расширенной матрице коэффициентов. При этом следует помнить, что перестановка столбцов равносильна переименованию неизвестных.
9
Обусловленность систем линейных алгебраических уравнений.
Если система плохо обусловлена, то это значит, что погрешности коэффициентов матрицы и свободных членов или погрешность округления при расчетах могут сильно
исказить решение. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Исходную систему уравнений |
A x |
b |
с учетом погрешности в векторе |
|
b |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Запишем как |
A (x x ) |
b b |
или |
|
A x |
b A x |
b |
|
и тогда |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
A x b |
отсюда можно выразить ошибку |
x A |
|
b |
|
|
|
|
||||||||||
|
|
|
|
|
|
|
1 |
|
|
|
|
1 |
|
|||||
Абсолютная погрешность |
|
|
|
|
|
|
|
|
||||||||||
|
|| x || || A |
b || или |
|
|| x || || A |
|
|| || b || |
||||||||||||
определим, как норму ошибки |
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Определим относительную погрешность |
|
|
|
|| x || || A |
|| || b || |
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|| |
x || |
|
|
|| x || |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Определим |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|| x || |
|
|
|
|
|
|
10 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
из исходной системы A x b получим |
|| A || || x || || b || |
||||||
|
далее определим |
|
|
|
|||
|
1 |
|
|
|
|
|
|
|
|
|| A || |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|| x || |
|| b || |
|
|
|
и подставим в определение относительной погрешности получим
|
1 |
|
|
|
|
|| x || |
|
|| b || |
|||
|
|
|| A |
|| || A || |
|
|
|
|||||
|| x || |
|
|
|
|| b || |
Вводим понятие числа обусловленности:
|
|
|
|
1 |
|
Kоб Cond(A) || A || |
|| A || |
||||
|
и тогда |
|
|
|
|
|
|
|
|
|
|
|| x || |
Kоб |
|| b || |
|||
|
|
|
|
|
|
|| x || |
|
|
|
|| b || |
|
11