Информатика_Методы
.pdf
21.01.2013
В соответствии с правилом умножения матриц рассмотренная система линейных уравнений может быть записана в матричном виде
|
|
А∙x = b |
, |
|
|
|
где: |
|
|
|
|
|
|
a11 |
a12 |
a1n |
x1 |
|
b1 |
|
|
|
|
|
|
|
|
A a21 |
a22 |
a2n , |
x x2 |
, |
b b2 |
|
|
|
|
|
|
|
|
|
|
|
... |
|
... |
|
an1 |
an2 |
ann |
xn |
bn |
||
71
71
21.01.2013
А - матрица коэффициентов системы;
b - матрица-столбец правой части системы;
х - матрица-столбец неизвестных.
Если матрица А - неособенная, то есть det A ≠ 0 ,то система или эквивалентное ей матричное уравнение имеет единственное решение.
72
72
21.01.2013
Идея метода Гаусса состоит в следующем. Исходную систему с матрицей коэффициентов A приводят путем эквивалентных преобразований (не изменяющих решение) к системе с треугольной матрицей:
x1 a12 x2 a1n xn b1 , |
|
|
x2 a2n xn b2 , |
|
|
|
|
|
|
|
|
|
ann xn bn , |
|
|
73
73
21.01.2013
Решение системы треугольного вида можно легко вычислить по рекуррентным формулам:
xn bn / ann , |
|
n |
|
xi bi ai j x j , |
(1) |
j i 1
(i n 1, n 2, , 1)
74
74
21.01.2013
Вычислительная процедура реализации данного метода состоит из прямого и обратного хода.
Прямой ход. Сначала нормируют первое уравнение, для этого его коэффициенты делят на a11. Затем первое уравнение умножают на первые коэффициенты всех ниже стоящих уравнений и последовательно вычитают из них. В результате x1 будет исключена из всех уравнений, кроме первого.
75
75
21.01.2013
Далее такая же процедура применяется к остальным n – 1 уравнениям. В результате система будет приведена к верхнему треугольному виду. Математически алгоритм прямого хода можно описать так.
На k-м шаге процесса исключения новые нормированные коэффициенты k-го уравнения (его называют ведущим) имеют вид
ak* j |
|
ak j |
и bk* |
b |
|
|
k |
, ( j = 1, 2,…, n), |
|||
ak k |
|
||||
|
|
|
ak k |
||
76
76
21.01.2013
Новые коэффициенты в уравнениях, стоящих ниже ведущего, принимают вид
ai*j ai j ai k ak* j
и b* b |
a |
i k |
b* |
|
i |
i |
|
k |
|
(i = k+1, 2,…, n, |
j = 1, 2,…, n). |
|||
Обратный ход. Значения неизвестных xi вычисляются по формулам (1).
77
77
21.01.2013
Применение метода Гаусса усложняется, если диагональный коэффициент ведущего уравнения равен нулю. В этом случае ведущее уравнение нельзя нормировать. Однако, изменив порядок, в котором расположены уравнения системы, эту трудность можно обойти.
78
78
21.01.2013
Можно также показать, что наименьшая погрешность округления достигается тогда, когда диагональный коэффициент (ведущий элемент) имеет наибольшее значение. Поэтому строку
снулевым или малым ведущим элементом надо заменить на ту из стоящих под ней строк, в которой в том же столбце стоит элемент, имеющий наибольшее значение. Такая процедура называется методом Гаусса
свыбором ведущего элемента.
79
79
начало |
ввод |
n |
ввод |
A[n,n],B[n] |
k=1, n-1, 1 |
j=k+1, n, 1 |
ak j ak j / akk |
bk bk / akk |
ak k 1 |
i=k+1, n, 1 |
j=k+1, n, 1
ai j ai j ak j ai k
bi bi bk ai k ai k 0
21.01.2013
ann 0 |
да |
|
|
нет |
|
xn bn / ann |
|
i=n-1, 1, -1 |
|
S 0 |
|
j=i+1, n, 1 |
S S ai j x j |
xi bi S
X[n]
конец
80
80