Материал: 730

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

где α = -aik/aii, i = 1, 2, 3, 4; k = 1, 2, 3, 4, 5.

Система является частным случаем записи вида

x1 =x2 =x3 =x4 =

	(L1x1, x2 , x3 , x4 ),
	(L2 x1, x2 , x3 , x4 ),	(*)
	(L3 x1, x2 , x3 , x4 ),	(*)
	(L3 x1, x2 , x3 , x4 ),
	(L4 x1, x2 , x3 , x4 ).

При этом линейная функция L1 фактически не зависит от х1.

Зададим какие-либо начальные значения неизвестных (нулевые приближения): х1(0), х2(0), х3(0), х4(0). Подставляя эти значения в правые

части системы (*), получим первые приближения:

x(1)		= L	(x(0)	, x(0)	, x(0) x(0) ),
	1	1	1	2	3	4
x2(1)		= L2 (x1(0) , x2(0)			, x3(0) x4(0) ),
		= L3 (x1(0) , x2(0)			, x3(0) x4(0) ),
x3(1)
x(1)		= L	(x(0)	, x(0)	, x(0) x(0) ).
	4	4	1	2	3	4
Полученные					первые приближения могут быть также

использованы для получения вторых, третьих и т. д. приближений.

Т.е. можно записать

, x3

= L1

(x1

, x2

(k )

(k−1)

x2(k )

= L2 (x1(k−1) , x2(k−1)

, x3(k−1) x4(k−1) ),

= L3 (x1(k−1) , x2(k−1)

, x3(k−1) x4(k−1) ),

x3(k )

x(k )

= L

(x(k−1)

, x(k−1)

, x(k−1) x(k−1) ).

Условие окончан я

терационного процесса при достижении

точности в упрощённой форме имеет вид

x(k+1) − x(k )

≤ε .

Условия сходимости итерационного процесса. Для того чтобы итерационный процесс сходился к точному решению, достаточно, чтобы все коэффициенты системы были малы по сравнению с диагональными.

2.5. Итерация Гаусса-Зейделя

Процесс итерации Якоби иногда можно модифицировать для ускорения сходимости.

Отметим, что итерационный процесс Якоби производит три последовательности – {х1(k)}, {х2(k)}, {х3(k)}. Кажется разумным, что

х1(k+1) может быть использовано вместо х2(k). Аналогично х1(k+1) и х2(k+1) можно использовать в вычислении х3(k+1).

3. Плохо обусловленные системы линейных алгебраических уравнений

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

виде A X = B.

Если система плохо обусловлена, то это значит, что погрешности коэффициентов матрицы А и правых частей B или же погрешности их округления сильно искажают решение системы.

Для оценки обусловленности системы вводят число обусловленности

M A = ∆A−1 ∆A.

Чем больше значение МА , тем система хуже обусловлена.

Свойства числа обусловленности:

МE =1.

МА ≥1.

МА ≥

λmax | / | λmin

, где

λmax ,

λmin –

соответственно

максимальное и минимальное собственные числа матрицы А.

МAB ≤ M A * M B .

5. Число обусловленностиАматрицы А не меняется при

умножении матрицы на про звольное число α ≠0.

Пусть в системе уравнен й возмущены коэффициенты матрицы

А и правая часть B, т.е.

~и

δA = A− A,

δB = B− B,δX =

X − X .

В качестве примера рассмотрим систему

1,03x1 +0,991x2 = 2,51;

(3.1)

0,943x2 = 2,41.

0,991x1 +

Решение этой системы

x* ≈1,981,

x* ≈ 0,4735.

Оценим влияние погрешности правых частей на результат.

Рассмотрим

“возмущенную”

систему

правой

частью

B* = (2,505; 2,415) и решим эту систему:

x* ≈ 2,877,

x* ≈ −0,4629.

Относительная погрешность правой части

δ(B) = 0,005/ 2,51 ≈ 0,28 % привела к относительной погрешности решения δ(X * ) = 0,9364 /1,981 ≈ 47,3%.

Погрешность возросла примерно в 237 раз. Число обусловленности системы (3.1) приблизительно равно 237.

Подобные системы называются плохо обусловленными. Возникает вопрос: какими методами можно решать такие

системы?

3.1. Метод регуляризации для решения плохо обусловленных систем

Рассмотрим систему

A X = B.

(3.2)

Для краткости перепишем эту систему в эквивалентной форме

(A X – B, A X – B) = 0.

(3.2)

Для примера рассмотрим систему

2x − x

=1;

x1 − 2x2

= 2.

Тогда ее можно представить как

(2x

− x

−1)2 +(x −2x

−2)2 = 0 .

(3.2*)

Решение системы (3.2) совпадает с решением системы (3.2*).

Если коэффиц енты А

ли B известны неточно, то решение также

является неточным, поэтомубвместо равенства (A X – B, A X –

B)=0

можем потребовать пр бл женного выполнения равенства (A X –

A X – B) ≈ 0 и в этомивиде з

адача становится

неопределенной

нужно добавить дополнительные условия.

В качестве дополнительного условия вводят требование, чтобы

решение как

можно меньше

отклонялось от

заданного x0 ,

т.е.

(x − x0 , x − x0 )

было минимальным. Следовательно, приходим

регуляризованной задаче вида

(Ax −b, Ax −b) +α(x − x0 , x − x0 ) = min,

(3.3)

где α>0.

Используя свойства скалярного произведения, выражение (3.3) перепишем в виде

(x, AT Ax) − 2(x, AT b) +(b,b) +α[(x, x) −2(x, x0 ) +(x0 , x0 )] = min. (3.4)

Варьируя Х в уравнении (3.4), получим уравнение вида

(AT A +αE)x = AT b +αx0.	(3.5)
Система (3.5) – система линейных алгебраических	уравнений,

эквивалентная системе (3.1). Систему (3.5) решаем с помощью метода Гаусса или с помощью метода квадратных корней. Решив систему (3.5), найдём решение, которое зависит от числа α.

Выбор управляющего параметра α.

Если α=0, то система (3.5) перейдёт в плохо обусловленную систему (3.1).

Если же α-велико, то система (3.5) переходит в хорошо обусловленную систему и решение этой системы может сильно отличаться от решения системы (3.1).

Оптимальное значение α – это такое число, при котором система

(3.5) удовлетворительно обусловлена.	И
На практике пользуются невязкой вида rα = AXα − B , и		эту
невязку сравнивают по норме с известной погрешностью правых
Д
частей δB и с влиянием погрешности коэффициентов матрицы δA.
Если α слишком велико, то rα >>δB или δA. Если α мало,		то

rα <<δB или δA.

Поэтому проводят серию расчетов, при различных α и в качестве
		б0
оптимального значения выбирают то значение α, когда выполнено
следующее условие:
	и
	rα		≈	δ B	А
					+	δA X	.
Для выбора вектора			x нужно знать приближенное решение или
С
же, если приближенное решен е трудно определить, то x0 = 0.
3.2. Метод вращения (Гивенса)

Метод Гивенса, как и метод Гаусса, состоит из прямого и обратного ходов.

Прямой ход метода. Исключаем неизвестное х1 из всех уравнений, кроме первого. Для исключения х1 из 2-го уравнения вычисляют числа

α12	=	a11			, β =		a21				,

		a2	+ a2				a2	+ a2
		11	21				11		21
где α и β такие, что α2						+ β2		=1,	− β			a	+α a	= 0.
				12			12			12		11	12	21

Первое уравнение системы заменяем линейной комбинацией

первого и второго уравнений с коэффициентами

α12

− β12 . В

результате получим систему

a(1) x

+ a

(1) x

+...

+ a(1) x

=b(1)

a22(1) x2

+...+ a2(1m) xm =b2(1) ,

+ a32 x2 +...+ a3m xm =b3 .

(3.6)

a31x1

. . . . . . . .

+ am2 x2

+...+ amm xm =bm .

am1x1

Здесь

a(1)

+ β

a(1)

=α

−

β a

b(1)

=α b

+ β

1 j

12 1 j

12 2 j

2 j

12 2 j

12 1 j

12 1

12 2

b(1)

− β

b ,

где j =

1, m

Преобразование

системы

(3.1)

к системе (3.6) эквивалентно

умножению слева матрицы А

и вектора B на матрицу С12 вида

Аналогично для исключения

х1

из третьего уравнения вычисляем

числа

a(1)

α13

β13

(1)

)

+ (a

(1)

)

+(a

)

(1)

такие, что α

+ β2

=1, α α

− β α91)

= 0.

Затем первое уравнение системы (3.6) заменяем линейной

комбинацией

первого

третьего

уравнений

с коэффициентами

α13 , β13 , а третьеСуравнение системы (3.6) заменяем линейной

комбинацией тех же уравнений, но с коэффициентами α13

и − β13.

Это преобразование эквивалентно умножению слева на матрицу

Исключая неизвестное х1 из всех последующих уравнений, получим систему

Смотрите также:

«ДОХОДЫ, РАСХОДЫ И ПРИБЫЛЬ КОММЕРЧЕСКОГО БАНКА.»
«ДОХОДЫ, РАСХОДЫ И ПРИБЫЛЬ КОММЕРЧЕСКОГО БАНКА.»
__RGR2
__RGR2
...Тянет нас вверх: топос в заключительных строках Фауста Гёте
...Тянет нас вверх: топос в заключительных строках Фауста Гёте
'Духовные песнопения' Уильяма Берда
'Румунський' напрям української дипломатії в 1917-1920 рр.: новітній етап історіографічних досліджень
[БИЛЕТЫ] Спланхнология
0-Технология доступа к данным ADO.NET

Материал: 730

2.5. Итерация Гаусса-Зейделя

3. Плохо обусловленные системы линейных алгебраических уравнений

3.1. Метод регуляризации для решения плохо обусловленных систем

3.2. Метод вращения (Гивенса)

Смотрите также: