Книги-online

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

И в библиотеке бывают рекламные паузы.

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

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

Процедура решает неоднородную систему n линейных алгебраических уравнений с n неизвестными:

	a11 x1+a12 x2+ . . .+a1n xn=a1n+1
	a21 x1+a22 x2+ . . .+a2n xn=a2n+1
	.	.	.	.
	an1 x1+an2 x2+ . . .+ann xn=ann+1

Процедура позволяет найти корни, если определитель основной матрицы A=(aij) не равен нулю. Для нахождения i-го корня ищем определитель:

для всех i=1..n. Тогда

В результате получим: если система не имеет решения, то S=0; если система имеет решения S=1, а массив X содержит решения системы. В процедуре вызывается функция вычисления определителя, в качестве которой можно использовать функцию приведенную здесь или другую имеющуюся у Вас. Наверх

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

Для удобства рассуждений систему запишем в матричном виде:

	Ax=b

где A=[aij]- квадратная матрица порядка n,

- векторы столбцы. Представим матрицу A в виде произведения нижней треуголной матрицы B=(bij) и верхней треугольной матрицы C=(cij) с единичной диагональю, т.е.

	A=BC

тогда искомый вектор x может быть вычислен из цепи уравнений

	By=b,	Cx=y

так как матрицы В и C - треугольные, то системы легко решаются.

Процедура не проверяет имеет ли система решение. Наверх

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

Процедура решает неоднородную систему n линейных алгебраических уравнений с n неизвестными:

	a11 x1+a12 x2+ . . .+a1n xn=a1n+1
	a21 x1+a22 x2+ . . .+a2n xn=a2n+1
	.	.	.	.
	an1 x1+an2 x2+ . . .+ann xn=ann+1

Вначале находим отличный от нуля коэффициент при x1. Соответствующее уравнение переставляем с первым (если это необходимо). Получаем систему с a11 отличным от нуля. Разделив коэффициенты этого уравнения на a11, получим:

	x1+b12 x2+ . . .+b1n xn=b1n+1

При помощи этого уравнения исключаем x1 из исходной системы:

	a(1)22 x2+a(1)23 x3+ . . .+a(1)2n xn=a(1)2n+1
	.	.	.	.
	a(1)n2 x2+a(1)n3 x3+ . . .+a(1)nn xn=a(1)nn+1

где

	a(1)i j=ai j-ai 1b1 j, i,j= 2...n

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

	x1+с12 x2+ . . .+с1n xn=с1n+1
	x2+ . . .+c2n xn=c2n+1
	.	.	.	.
	xn=cnn+1

Теперь легко определить xn,xn-1, . . ., x1.

Если det(A)=0, то исходная система не имеет решений и процедура выдает S=0 иначе S=1 и решения находятся в массиве X. Наверх

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

Процедура решает неоднородную систему n линейных алгебраических уравнений с n неизвестными:

	a11 x1+a12 x2+ . . .+a1n xn=a1n+1
	a21 x1+a22 x2+ . . .+a2n xn=a2n+1
	.	.	.	.
	an1 x1+an2 x2+ . . .+ann xn=ann+1

В отличии от предыдущего алгоритма на каждом шаге мы ищем не просто отличный от нуля коэффициент при xk, а максимальный из них по абсолютной величине, в остальном практически таже схема приведения системы к треугольному виду:

	с11x1+с12 x2+ . . .+с1n xn=с1n+1
	с22x2+ . . .+c2n xn=c2n+1
	.	.	.	.
	сnnxn=cnn+1

Если det(A)=0, то исходная система не имеет решений и процедура выдает S=0 иначе S=1 и решения находятся в массиве X. Выбор на каждом шаге максимального по абсолютной величине коэффициента, позволяет получить малые невязки при решении системы. Наверх

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

Вновь решаем систему n линейных уравнений Ax=b. Вначале приведем матрицу A к нижне-треугольному виду преобразованиями вращения:

	A=L*Rn-1 n ... R1 2

здесь L - нижняя треугольная матрица (т.е. элемент li j=0, если j > i), а Ri j - матрица вращения. Матрица вращения это "почти единичная" матрица у которой ri i=rj j=cos(u), и ri j=-rj i=sin(u). Действительно нетрудно проверить, что умножая, например, матрицу 2-го порядка

	   | cos(u) sin(u)|
	R= |              |
	   |-sin(u) cos(u)|

на некоторый вектор x, мы осуществим поворот этого вектора на угол u относительно начала координат. Заметим, что определитель матрицы врщения равен 1, и Ri j*RTi j=E, т.е. обратная матрица совпадает с транспонированной.

Итак представив исходную матрицу в виде произведения нижней треугольной матрицы на последовательность матриц вращения, мы можем решить вначале систему Ly=b, а затем систему Rn-1 n ... R1 2x=y. Первая система легко решается благодаря простому виду матрицы L, а вторую систему нетрудно разрешить, благодаря свойствам матрицы вращения.

Несколько слов непосредственно о реализации алгоритма. Вначале последовательно для каждого ненулевого элемента расположенного выше главной диагонали матрицы A находится преобразование вращения, которое переводит его в нуль. Для хранения преобразование вращения Ri j достаточно хранить соответствующий угол u, но проще хранить t=tg(2u), тогда

	cos(u)=(1-t2)/(1+t2)
	sin(u)=2t/(1+t2)

В результате последовательности преобразований, в массиве A будет, непосредственно матрица L(a[i,j]=li j, i≥j; li j=0, i< j) и соответствующие преобразование Ri j (a[i,j]=ti j, i<j, здесь ti j - тангес удвоенного угла вращения для преобразования Ri j). Теперь решаем вначале систему Ly=b, а затем из вектора y, получаем решения исходной системы обращая преобразования вращения. Наверх

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

Вновь решаем систему n линейных уравнений Ax=b. Вначале приведем матрицу A к верхне-треугольному виду преобразованиями отражений:

	Qn-1 ... Q2*Q1*A*S = R,

здесь Qi - соответствующие матрицы отражения, S -результирующая матрица перестановок, R - верхняя треугольная матрица.

Теперь решив треугольную систему

	R*Y=Qn-1 ... Q2*Q1*b

нетрудно определить решение исходной системы

	X=S*Y

Чуть подробнее о реализации алгоритма. Вначале находим преобразования отражения, применяя их к матрице A и вектору b. Затем решаем полученную систему, помещая решение в вектор X, и, наконец, переставляем элементы вектора X используя вектор S, который содержит информацию о перестановках в исходной матрице A. Наверх