Лабораторная работа №6. Решение систем линейных уравнений Решение систем линейных уравнений методом Гаусса

Базовый метод Гаусса предназначен для решения систем линейных уравнений.

Пример системы линейных уравнений:

(*)

Систему линейных уравнений в общем виде можно записать в следующем виде (1).

(1)

Формулу (1) можно переписать в сокращенных обозначениях:

A ·X=B

Рассмотрим процесс получения коэффициентов матрицы A для системы линейных уравнений (*):

1 шаг

2 шаг

заполняем матрицу А

для первого уравнения системы (*)

5x₁+x₂+3x₄=3

для второго уравнения (*) x₂+x₃-x₁=2

Таким образом, вся система уравнений (*) может быть записана в виде равенства произведения матрицы коэффициентов A и столбеца неизвестных X столбцу правых частей B:

В матричном виде можно записать несколько систем линейных уравнений, если у них матрица А одна и та же, а вектора правых частей различные.

Пример

Формально решение системы линейных уравнений АХ=В можно получить, умножив обе части этого уравнения на обратную матрицу А^-1. В левой части получится единичная матрица, умноженная на вектор Х, а в правой части – А^-1В

Е Х=А^-1В.

Е Х= Х, таким образом, решение системы линейных уравнений имеет вид:

Х=А^-1В.

Определение обратной матрицы, если система линейных уравнений имеет большой порядок – трудоемкий процесс.

Существуют различные численные методы для решения систем линейных уравнений, из них часто используются – прямой метод Гаусса, итерационный метод Гаусса-Зейделя.

Метод Гаусса (базовый) состоит из двух этапов:

1. Приведение системы линейных уравнений к треугольному виду.

Треугольный вид

2. Определение вектора решения.

Последнее уравнение имеет вид . Откуда легко найти значение х_n:

теперь можно получить неизвестные x_n-1

x_n в уже известен, перенесем это слагаемое в правую часть

………………………………………..

Рассмотрим строку с номером k.

обозначим уже известные величины s_k =

, где j=k+1, k+2,…,n

n+1>n

Алгоритм определения х_i

Цикл по i от n до 1 с шагом -1

Конец Цикла

Детализируем этот фрагмент

s_i=0

Цикл по j от i+1 до n c шагом 1

s_i=s_i+ ∙x_j

Конец Цикла

Здесь s_i можно обозначить как s

(**) Цикл по i от n до 1 с шагом -1

s =0

Цикл по j от i+1 до n с шагом 1

Конец Цикла……………………

Конец Цикла

Этот цикл при i=n будет выглядеть следующим образом

Цикл по j от n+1 до n с шагом 1

Конец Цикла

и не выполнится ни разу, так как начальное значение j больше конечного.

Для проверки фрагмента (**) можно создать специальную систему уравнений с треугольной матрицей и решить ее.

Рассмотрим процедуру получения (приведения) треугольной матрицы (приведения исходной системы линейных уравнений к треугольному виду).

(1)

(2)

1-й шаг. Преобразуем все уравнения, кроме первого, таким образом, чтобы элементы первого столбца стали нулевыми.

Преобразованное первое уравнение имеет вид:

(1)′=((1)/a₁₁)·a₂₁

(2)′=(2)-(1)·a₂₁/a₁₁

(3)′=(3)-(1)·a₃₁/a₁₁

….

(n)′=( n)-(1)·a_n-1/a₁₁

Здесь (1) – первое уравнение исходной системы линейных уравнений; (1)', (2)', (3)', …, (n)' – преобразованные (1), (2), (3), …, (n) уравнения первоначальной системы.

Базовая строка = строка (1)

Цикл по i от 2 до n

Новая строка (i)=Старая Строка (i)-Строка(1)·Первый Элемент Старой Строки (i)/ Первый Элемент Базовой Строки

Конец Цикла

или

k=1-номер базовой строки

Цикл по i от k+1 до n

С трока (i)=Старая Строка (i)-Строка(k)·Старая Строка (i)(k)/Строка(k)(k)

Конец Цикла

или

k=1

Цикл по i от k+1 до n

p=a(i,k)/a(k,k)

Цикл по j от k до n

a(i,j)= a(i,j)- a(k,j)∙p (***)

Конец Цикла

b(i)=b(i)-b(k)∙p

Конец Цикла

Процедуру (***) необходимо повторить для всех базовых строк, для всех k от 1 до n–1.

Цикл по k от 1 до n-1

Цикл по i от k+1 до n

p=a(i,k)/a(k,k)

Цикл по j от k до n

a(i,j)= a(i,j)- a(k,j)∙p

Конец Цикла

b(i)=b(i)-b(k)∙p

Конец Цикла

Конец Цикла

Это базовый алгоритм приведения системы линейных уравнений к треугольному виду. Базовый алгоритм будет работать в том случае, когда диагональные элементы матрицы a_i,j не равны нулю.

Базовый алгоритм метода Гаусса в общем виде выглядит следующим образом:

n=… ← задание размерности матрицы

Объявление матрицы а(n,n)

Объявление вектора b(n)

Объявление вектора x(n)

Задаем матрицу а(n,n)

Задаем вектор b(n)

Ц икл по k от 1 до n-1 c шагом 1

Цикл по i от k+1 до n c шагом 1

p=a(i,k)/a(k,k)

Цикл по j от k до n c шагом 1 (****)

a(i,j)= a(i,j)- a(k,j)∙p

Конец Цикла

b(i)=b(i)-b(k)∙p

Конец Цикла

Конец Цикла

Цикл по i от n до 1 c шагом -1

s=0

Цикл по j от i+1 до n c шагом 1

s=s+a(i,j)∙x(j)

Конец Цикла

x(i)=(b(i)-s)/a(i,i)

Конец Цикла

Печать вектора x(i)

Ниже приведен пример головной программы решения системы линейных уравнений с помощью базового метода Гаусса на языке VFP. Матрица задается генератором случайных чисел.

n=20

DIMENSION a(n,n), a1(n,n), a2(n,n), b(n),b1(n),x1(n),x(n)

SET DECIMALS TO 5

With _screen

.Cls

.FontName = “Название шрифта”

.FontSize = Размер шрифта

Endwith

Получить_матрицу(@a,n,1,10)

Получить_вектор(@b,n,0,10)

печ_матр_гаусс(@a,@b,n)

гаусс(@a,@b,@x,n)

? "x="

печ_вект(@x,n)

умн_матр_вект(@a1,@x,@x1,n)

? "b1="

печ_вект(@b1,n)

? "x1="

печ_вект(@x1,n)