Относительная ошибка решения слау

Влияние обусловленности матрицы на точность решения системы с ней

В этом разделе мы рассмотрим, как ошибки
в элементах вектора правой части и в
матрице системы линейных уравнений Ax
= b могут повлиять на решение этой системы.
Обратимся сначала к случаю внесения
возмущений в вектор правой части b. Итак,
мы решаем две системы

причем предполагается, что каждую из
систем мы решаем точно, а основной
возникающий вопрос — насколько будет
отличаться решение x системы (1) от решения
системы (2) с возмущением в правой части
δb. Это довольно важный вопрос, поскольку
элементы правой части могут быть получены
как результат некоторых измерений,
соответственно содержащий погрешность
δbk в каждой компоненте bk. Хотелось бы,
чтобы при измерении одной и той же
величины (каждый раз со своими, небольшими
погрешностями) соответствующие решения
систем с мало отличающимися правыми
частями также не очень сильно отличались
друг от друга. К сожалению, так бывает
не всегда. Причиной этому — характеристика
матрицы, называемая ее обусловленностью.
Об этом и пойдет дальше речь.

Сначала требуется ввести меру близости
векторов
и
x, т.е. вектора ошибки

. Мерой величины вектора является норма
(определяться она может по-разному).
Возьмем пока в качестве нормы обычную
евклидову норму вектора (квадратный
корень из суммы квадратов его компонент),
т.е.

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

где n — число неизвестных и уравнений
в системе. Кроме векторной нормы для
оценки величины вектора нам понадобится
еще и матричная норма для оценки величины
матрицы. Возьмем матричную норму, которая
определяется следующим образом (она
называется спектральной):

т.е. спектральная матричная норма равна
квадратному корню из максимального
собственного числа матрицы ATA. В MATLAB
имеется функция norm для вычисления норм
матриц и векторов, которая, в частности,
умеет вычислять приведенные выше нормы.
Почему мы выбрали именно такие нормы
векторов и матриц, подробно объясняется
в разделе Получение неравенства для
ошибки, согласованная норма матрицы,
где приведено немного выкладок и
определений. Это связано с оценкой,
которой мы будем пользоваться для ошибки
в решении системы (вывод этого неравенства
также приведен в упомянутом разделе):

Здесь через обозначено число обусловленности
матрицы , которое определяется так:

Из приведенного неравенства следует,
что чем больше число обусловленности
матрицы системы, тем больше может быть
относительная ошибка в решении

при небольшой ошибке в правой части

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

Для создания матрицы Гильберта в MATLAB
предусмотрена функция hilb, входной
аргумент которой задает размер матрицы.
Возьмем небольшую матрицу 6 на 6:

n = 6;

H = hilb(n)

H =

1.0000 0.5000 0.3333 0.2500 0.2000 0.1667

0.5000 0.3333 0.2500 0.2000 0.1667 0.1429

0.3333 0.2500 0.2000 0.1667 0.1429 0.1250

0.2500 0.2000 0.1667 0.1429 0.1250 0.1111

0.2000 0.1667 0.1429 0.1250 0.1111 0.1000

0.1667 0.1429 0.1250 0.1111 0.1000 0.0909

Далее вычислим такую правую часть
системы b, что все компоненты ее решения
x равны единице:

x =
ones(n, 1);

b =
H*x

b =

2.4500

1.5929

1.2179

0.9956

0.8456

0.7365

Видим, что ни в матрице, ни в векторе
правой части нет ничего «подозрительного»,
все числа не сильно отличаются друг от
друга. Теперь сформируем возмущенную
правую часть b + δb, добавив в вектор b
небольшие числа порядка 10-5 и решим
систему с возмущенной правой частью
для получения вектора .

delta_b
= 1e-5*(1:n)’;

x_tilda
= H(b + delta_b)

x_tilda =

0.9978

1.0735

0.4288

2.6632

-1.0160

1.8593

Видно, что полученное решение далеко
от точного, где должны быть все единицы.
Вычислим относительную ошибку в решении
и в правой части (функция norm по умолчанию
вычисляет евклидову норму вектора):

delta_x
= x — x_tilda;

LEFT
= norm(delta_x)/norm(x)

LEFT
=

1.1475

RIGHT
= norm(delta_b)/norm(b)

RIGHT =

2.7231e-005

Итак, ошибка в решении порядка единицы,
хотя изменения в правой части были
порядка 10-5. Это полностью укладывается
в приведенное выше неравенство для
ошибки. Действительно, вычислим число
обусловленности cond(H) при помощи функции
MATLAB, которая называется cond и по умолчанию
вычисляет

для спектральной нормы матрицы

c = cond(H)

c =

1.4951e+007

Итак

= LEFT ≈ 1.1475 меньше

= c* RIGHT ? 1.4951e+07 * 2.7231e-05 ≈ 407

и неравенство выполнено (даже с некоторым
запасом).

При увеличении размера матрицы Гильберта
ошибка в решении будет только расти
(это несложно проверить, задавая n = 7, 8,
…). Причем, при n = 12 выведется сообщение
о том, что матрица плохообусловлена и
решение может оказаться неверным

Warning:
Matrix is close to singular or badly scaled.

Results
may be inaccurate. RCOND = 2.409320e-017.

В качестве меры обусловленности здесь
выбрана величина RCOND равная единице,
деленной на оценку числа обусловленности
(число обусловленности оценивается по
достаточно быстрому алгоритму, который
работает намного быстрее, чем cond, о чем
более подробно написано в справке по
функции rcond). Если значение RCOND мало, то
матрица считается плохообусловленной.

Увеличение ошибки в решении при увеличении
размера матрицы Гильберта происходит
из-за того, что число обусловленности
матрицы Гильберта растет очень быстро
с ее размером. В этом несложно убедиться
при помощи простого цикла и функции
semilogy (масштаб по оси ординат —
логарифмический):

N =
1:20; C = zeros(1, 20);

for
n = N

H = hilb(n);

C(n) = cond(H);

end

semilogy(N, C)

grid
on, title(‘cond(H)’), xlabel(‘n’)

Кстати, поскольку функция cond находит
число обусловленности при помощи
численного метода (а именно сингулярного
разложения для нахождения сингулярных
чисел), то число обусловленности после
n = 12 вычисляется уже неверно, на самом
деле оно должно расти и дальше, в чем
можно убедиться при помощи символьных
вычислений в MATLAB и операций с заданным
числом значащих цифр

N =
1:20; C = zeros(1, N);

digits(60)

for n = N

H = vpa(sym(hilb(n))); % вычисление матрицы
Гильберта с точностью до 60-го знака

sigma = svd(H); % нахождение сингулярных
чисел матрицы Гильберта

% вычисление числа обусловленности
матрицы Гильберта

C(n) = max(double(sigma))/min(double(sigma));

end

semilogy(N, C)

grid
on, title(‘cond(H)’), xlabel(‘n’)

Рассмотрим теперь три важных момента,
касающихся данного примера.

Первый из них — решение системы Hx = b (с
вектором правой части, соответствующим
решению из единиц) при помощи оператора
обратной косой черты не даст точные
единицы, погрешность будет уже в десятом
знаке (хотя в MATLAB все вычисления по
умолчанию выполняются с двойной
точностью)

format
long

ans
=

0.99999999999916

1.00000000002391

0.99999999983793

1.00000000042209

0.99999999953366

1.00000000018389

Так происходит из-за того, что при
вычислении вектора b при умножении
матрицы H на вектор из всех единиц мы
уже заложили в него некоторую погрешность.
Кроме того, ошибки округления в процессе
решения системы также сыграли свою роль
и плохая обусловленность матрицы (даже
небольшого размера) привела к таким
ошибкам в решении. Действительно, для
матриц небольшого размера с небольшим
числом обусловленности такого эффекта
наблюдаться не будет. Возьмем матрицу
6 на 6 из случайных чисел, вычислим ее
число обусловленности

A = rand(n);

cond(A)

ans =

57.35245279907571

Затем сформируем правую часть,
соответствующую точному решению из
всех единиц

x = ones(n, 1);

b = A*x;

и решим систему, получив в результате
хорошую точность

>> Ab

ans =

1.00000000000000

Второй важный момент связан с определителем
матрицы. Вычислим определитель матрицы
Гильберта размера 6 на 6, с которой мы
решали систему

>> det(hilb(6))

ans =

5.3673e-018

Определитель оказывается достаточно
мал, откуда можно сделать неверный
вывод, что источник проблемы большой
ошибки в решении при небольшом возмущении
правой части системы — малость
определителя. В действительности это
не так, если определитель системы мал,
то это не означает плохой обусловленности
матрицы и, следовательно, большой ошибки
в решении. Действительно, возьмем матрицу

A = [1e-40 1e-42 1e-42

1e-42 1e-40 1e-42

1e-42 1e-42 1e-40];

Ее определитель очень мал, порядка
10-121

det(A)

ans =

9.9970e-121

(слово «очень», конечно условно, но он
меньше определителя матрицы Гильберта
размера 6 на 6, при решении системы с
которой у нас возникли проблемы). Однако,
малость определителя никак не повлияет
на ошибку в решении при возмущении
правой части системы, что несложно
показать, сформировав систему с известным
решением, внеся возмущения в правую
часть и решив систему:

x =
[1e40; 1e40; 1e40];

b =
A*x;

delta_b
= 1e-5*[1; 2; 3];

x_tilda
= A(b+delta_b);

delta_x
= x — x_tilda;

LEFT
= norm(delta_x)/norm(x)

RIGHT
= norm(delta_b)/norm(b)

LEFT =

2.1272e-005

RIGHT =

2.1179e-005

Итак, относительная ошибка в решении
практически равна относительной ошибке
в правой части, поскольку число
обусловленности приведенной выше
матрицы A немного больше 1, а именно:

c = cond(A)

c =

1.0303

И, наконец, рассмотрим третий вопрос,
касающийся достижения знака равенства
в неравенстве для ошибки в решении

Т.е., говоря другими словами, выясним:
может ли быть такая ситуация, когда мы
делаем небольшое относительное возмущение
правой части системы, скажем 10-5, число
обусловленности матрицы системы равно
1010, а в решении получается относительная
ошибка 105. Можно проделать массу примеров,
перебирая различные матрицы, не получить
достижения равенства и ошибочно
заключить, что это всего лишь завышенная
оценка сверху для ошибки в решении.
Однако, это не так, в чем нас убеждает
следующий пример

A = [2.1005632211074903e+009 2.4405728346208658e+009
2.6288320556007657e+009 3.9543845780862803e+009

5.6384551998346877e+008
6.5511289861702812e+008 7.0564654322518432e+008
1.0614591390422670e+009

1.9531852931707768e+009 2.2693394431935925e+009
2.4443901805698233e+009 3.6769404175323849e+009

2.2044117415857959e+009 2.5612308917984776e+009
2.7587973499916158e+009 4.1498830928366508e+009];

b =
[ -5.7373057243726833e-001

-1.5400413072907607e-001

-5.3347697688693385e-001

-6.0209490373259589e-001];

delta_b
= [-0.71685839091451e-5

0.54786619630709e-5

0.37746931527138e-5

0.20850322383081e-5];

в котором относительное возмущение
правой части равно 10-5

RIGHT
= norm(delta_b)/norm(b)

RIGHT =

1.0000e-005

Относительная ошибка в решении системы
оказывается 105

x =
Ab;

x_tilda
= A(b+delta_b);

delta_x
= x — x_tilda;

LEFT
= norm(delta_x)/norm(x)

LEFT =

1.0000e+005

И происходит так потому, что

1) в этом примере число обусловленности
матрицы A равно 1010;

c = cond(A)

c =

1.0000e+010

2) неравенство для ошибки в решении
переходит в равенство.

Если установить формат long, то мы увидим,
что LEFT, RIGHT и число обусловленности не
в точности 105, 10-5 и 1010, соответственно,
но это вызвано ошибками округлений. При
решении в точной арифметике, равенство
получилось бы точным, что можно показать
аналитически (см. раздел Получение
неравенства для ошибки, согласованная
норма матрицы, подробнее про norm и cond).

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

Ax = b

мы решаем систему

В этом случае мы так же можем оценить
погрешность в решении, и в оценку снова
входит число обусловленности матрицы

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

Источник

2.3. Обусловленность СЛАУ. Число обусловленности матрицы

Понятия согласованных норм матриц и векторов позволяют оценить погрешности,
возникающие при численном решении СЛАУ. Пусть и матрица, и правая часть системы заданы с некоторой погрешностью, тогда наряду с системой

(
2.4)

рассматривается система

(mathbf{A}+ Deltamathbf{A})(mathbf{u}+ Deltamathbf{u}) = mathbf{f}+ Deltamathbf{f}.

(
2.5)

Теорема. Пусть правая часть и невырожденная матрица СЛАУ (2.4)
вида $mathbf{Au}= mathbf{f}, mathbf{u} in L^n, mathbf{f} in L^n$ , получили приращения Deltamathbf{f} и Deltamathbf{A} соответственно. Пусть существует обратная матрица $mathbf{A}^{-1}$ и выполнены условия

$|mathbf{A}| ne 0, mu frac{|mathbf{Delta A}|}{|mathbf{A}|}< 1$

, где $mu = |mathbf{A}| cdot left|{mathbf{A}^{- 1}}right| .$ В этом случае оценка относительной погрешности решения |{Deltamathbf{u}}|/|mathbf{u}| удовлетворяет
неравенству

$frac{|Deltamathbf{u}|}{|mathbf{u}|} le frac{mu} {1 - mu frac{|Deltamathbf{A}|}{|mathbf{A}|}} left({frac{|Delta mathbf{f}|}{|mathbf{f}|}+ frac{|Deltamathbf{A}|} {|mathbf{A}|}}right).$

Доказательство.

Из (2.5) следует, что $Deltamathbf{u} = {mathbf{A}}^{- 1}(Deltamathbf{f}- Deltamathbf{A} mathbf{u}- Deltamathbf{A} Deltamathbf{u}).$ Переходя в этом равенстве к норме и использовав неравенство треугольника, получаем

$|{Deltamathbf{u}}| le left|{mathbf{A}^{- 1}}right| |{Deltamathbf{f}}| + left|{mathbf{A}^{- 1}}right| |{Deltamathbf{A}}| |mathbf{u}| + left|{mathbf{A}^{- 1}}right| |{Deltamathbf{A}}| |{Deltamathbf{u}}| , mbox{ или } \ |{Deltamathbf{u}}| le left|{mathbf{A}^{- 1}}| frac{|Deltamathbf{f}|}{|mathbf{f}|} |mathbf{f}| + left|{mathbf{A}^{- 1}}right| frac{|Deltamathbf{A}|}{|mathbf{A}|} |mathbf{A}| |mathbf{u}| + left|{mathbf{A}^{- 1}}right| frac{|Deltamathbf{A}|}{|mathbf{A}|} |Deltamathbf{u}|.$

Вводя обозначение $mu (mathbf{A}) = left|{mathbf{A}^{- 1}}right| cdot |mathbf{A}|$ , перепишем последнее равенство в виде

$|Deltamathbf{u}| left(1 - mu frac{|Deltamathbf{A}|} {|mathbf{A}|}right) le mu frac{|Delta mathbf{f}|}{|mathbf{f}|} frac{|mathbf{f}|}{|mathbf{A}|} + mu cdot frac{|Delta mathbf{A}|} {|mathbf{A}|} |mathbf{u}| le \ le mu frac{|Deltamathbf{f}|}{|mathbf{f}|} |mathbf{u}| + mu frac{|Deltamathbf{A}|}{|mathbf{A}|} |mathbf{u}| = mu left(frac{|Deltamathbf{f}|}{|mathbf{f}|} + frac{|Deltamathbf{A}|}{|mathbf{A}|}right) |mathbf{u}| .$

Заметим, что

$frac{|mathbf{f}|}{|mathbf{A}|} le |mathbf{u}|$

т.к. |mathbf{f}| = |mathbf{Au}| le |mathbf{A}| cdot |mathbf{u}|.

Тогда для оценки относительной погрешности решения окончательно получим

$frac{|Deltamathbf{u}|}{|mathbf{u}|} le frac{mu} {1 - mu frac{|Deltamathbf{A}|}{|mathbf{A}|}} (frac{|Deltamathbf{f}|}{|mathbf{f}|} + frac{|Deltamathbf{A}|}{|mathbf{A}|}).$

(
2.6)

При Delta A approx 0 получаем оценку при наличии погрешности только правых частей

$frac{|Deltamathbf{u}|}{|mathbf{u}|} le mu frac{|mathbf{Delta f}|}{|mathbf{f}|},$

(
2.7)

если в (2.5) положить Deltamathbf{A} cdot Delta mathbf{u} approx 0 , то

$frac{|Deltamathbf{u}|}{|mathbf{u}|} le mu (frac{|Deltamathbf{f}|}{|mathbf{f}|} + frac{|Deltamathbf{A}|}{|mathbf{A}|}).$

(
2.8)

В результате получено важное соотношение, показывающее, на сколько возрастают относительные ошибки решения СЛАУ в случае наличия относительных ошибок при задании правых частей и элементов матриц.

Величина

$mu (mathbf{A}) = left|{mathbf{A}^{- 1}}right| |mathbf{A}|}$

(
2.9)

называется числом обусловленности матрицы mathbf{A}. Число обусловленности определяет, насколько погрешность входных данных может повлиять на решение системы (2.1) . Почти очевидно, что всегда mu ge 1. Действительно

$1 = |mathbf{E}| = left|{mathbf{A^{-1}A}}right| le left|mathbf{A^{-1}}right| |mathbf{A}| = mu.$

При mu approx 1 div 10 ошибки входных данных слабо сказываются на решении и система (2.1) считается хорошо обусловленной. При $mu > > 10^{2} div 10^{3}$ система является плохо обусловленной.

Пример. Решением системы

$left{ begin{array}{l} 100u + 99v = 199 \ 99u + 98v = 197 \ end{array} right.$

будет пара чисел u = v = 1.

Внесем возмущение в правые части системы:

$left{ begin{array}{l} 100u + 99v = 198,99 \ 99u + 98v = 197,01. \ end{array} right.$

При этом решение заметно изменится: u = 2,97; v = -0,99. Воспользовавшись выбранными согласованными нормами, получим

$begin{gather*} {|mathbf{f}|}_1 = 199,quad {|Deltamathbf{f}|}_1 = 10^{- 2}, \ delta f = frac{{|Deltamathbf{f}|}_1}{{|mathbf{f}|}_1} approx 0,5 cdot 10^{- 4} mbox{ (это очень малая величина),} \ {|mathbf{A}|}_1 = {left|mathbf{A}^{- 1}right|}_1 = 199, mu = 199 cdot 199 approx 4 cdot 10^4 . end{gather*}$

Значит,

$delta u = frac{|Deltamathbf{u}|}{|mathbf{u}|} le mu frac{|Deltamathbf{f}|}{|mathbf{f}|} approx 4 cdot 10^4 cdot frac{10^{- 4}}{2}= 2$

, что согласуется с результатами решения возмущенной и невозмущенной задач. Для невозмущенной задачи |Deltamathbf{u}| approx 2 , |mathbf{u}| = 1.

Рассмотрим еще одно важное свойство. Число обусловленности матрицы, как
было показано ранее, можно определить, как delta u/delta f le mu (mathbf{A}) , если Deltamathbf{A} approx {mathbf0} при

$$ delta u = frac{|Deltamathbf{u}|}{|mathbf{u}|}$.$

Можно ли найти более тонкую оценку отношения delta u/delta f , учитывающую зависимость обусловленности СЛАУ от выбора правых частей? В этом случае параметр обусловленности системы, вообще говоря, зависит и от mathbf{f} , и
от Delta mathbf{f} , и удовлетворяет неравенству

$$ nu(mathbf{f},Deltamathbf{f}) ge frac{delta u}{delta f} = frac{|Deltamathbf{u}|}{|mathbf{u}|} cdot frac{|mathbf{f}|} {|Deltamathbf{f}|} $.$

Его можно определить как точную верхнюю грань отношения

$frac{delta u}{delta f}$

по Delta mathbf{f} , что соответствует наихудшей ситуации. Тогда

$nu (mathbf{f}) = suplimits_{Deltamathbf{f}} frac{|Deltamathbf{u}|}{|mathbf{u}|} frac{|mathbf{f}|}{|Deltamathbf{f}|} = suplimits_{Deltamathbf{f}} frac{|mathbf{f}|}{|mathbf{u} |} frac{|Deltamathbf{u}|}{|Deltamathbf{f}|} = \ = frac{|mathbf{f}|}{|mathbf{u}|} suplimits_{Deltamathbf{f}} frac{left|mathbf{A}^{- 1}Deltamathbf{f}right|}{|Deltamathbf{f}|} = frac{|mathbf{f}|}{|mathbf{u}|} left|{mathbf{A}^{- 1}}right| .$

Далее,

$suplimits_mathbf{f} left|{mathbf{A}^{- 1}}right| cdot frac{|mathbf{f}|}{|mathbf{u}|} = left|{mathbf{A}^{- 1}}right| cdot suplimits_mathbf{f} frac{|Amathbf{u}|}{|mathbf{u}|} = left|{mathbf{A}^{- 1}}right| cdot |mathbf{A}| = mu (mathbf{A}),$

с другой стороны

$inflimits_mathbf{f}nu (mathbf{f}) = inflimits_mathbf{f} left|{mathbf{A}^{- 1}}right| cdot frac{|mathbf{f}|}{|mathbf{u}|} = inflimits_mathbf{f} left|{mathbf{A}^{- 1}}right| suplimits_mathbf{f} {left(frac{|mathbf{u}|}{|mathbf{f}|}right)}^{- 1} = \ = left|{mathbf{A}^{- 1}}right| {left(suplimits_mathbf{f}frac{left|{mathbf{A}^{- 1}mathbf{f}}right|}{|mathbf{f}|}right)}^{- 1} = 1.$

Параметр nu (mathbf{f}) , характеризующий обусловленность системы, зависит от правых частей. Более тонкая его оценка есть

$nu (mathbf{f}) = left|{mathbf{A}^{- 1}}right| frac{|mathbf{f}|}{|mathbf{u}|}$

, причем 1 le nu (mathbf{f}) le mu . Так как такую оценку провести не всегда возможно, то чаще используется точная верхняя грань $left|{mathbf{A}^{- 1}} right| |mathbf{A}|.$ Такая оценка, конечно, может быть существенно завышенной.

Можно также показать, что для симметричной матрицы mathbf{A} имеет место $mu = left|{maxlimits_k lambda_{mathbf{A}}^k}right| / left|{minlimits_k lambda_{mathbf{A}}^k}right|$ , т.е. обусловленность СЛАУ зависит от ее спектральных свойств. Это следует из определения третьей нормы матрицы ${|mathbf{A}|}_3 = left|{maxlimits_k lambda_{mathbf{A}}^k}right|$
и соотношения

${left|{mathbf{A}^{- 1}}right|}_3 = {left|{minlimits_k lambda_{mathbf{A}}^k}right|}^{- 1}$

, которое предлагается доказать самостоятельно.

Источник

Методы решения систем линейных алгебраических уравнений (СЛАУ) с примерами

Содержание:

Методы решения систем линейных алгебраических уравнений (СЛАУ)

Метод Крамера

Определение: Системой линейных алгебраических уравнений (СЛАУ) называется выражение

Определение: Определитель, составленный из коэффициентов при неизвестных, называется главным определителем системы

Крамер предложил следующий метод решения СЛАУ: умножим главный определитель на для этого умножим все элементы первого столбца на эту неизвестную:

Второй столбец умножим на третий столбец — на -ый столбец — на и все эти произведения прибавим к первому столбцу, при этом произведение не изменится:

Согласно записи СЛАУ первый столбец получившегося определителя представляет собой столбец свободных коэффициентов, т.е.

Определение: Определитель называется первым вспомогательным определителем СЛАУ.

Поступая аналогично тому, как описано выше, найдем все вспомогательные определители СЛАУ:

31. Для того чтобы найти вспомогательный определитель i, надо в главном определителе СЛАУ заменить столбец i на столбец свободных коэффициентов.

Определение: Полученные выше соотношения называются формулами Крамера. Используя формулы Крамера, находят неизвестные величины Проанализируем полученные формулы:

Пример:

Решить СЛАУ методом Крамера

Решение:

Прежде всего, обращаем внимание на то, что в последнем уравнении переменные записаны в неправильном порядке, в этом случае говорят, что СЛАУ записана в ненормализованном виде. Нормализуем СЛАУ, для чего запишем неизвестные в последнем уравнении системы в правильном порядке, чтобы одноименные неизвестные были записаны друг под другом

Найдем главный определитель СЛАУ (раскрываем по первой строке)

Так как главный определитель системы отличен от нуля, то СЛАУ имеет единственное решение. Найдем три вспомогательных определителя

Воспользуемся формулами Крамера

Замечание: После нахождения решения СЛАУ надо обязательно провести проверку, для чего найденные числовые значения неизвестных подставляется в нормализованную систему линейных алгебраических уравнений.

Выполним проверку Отсюда видно, что СЛАУ решена верно.

Матричный способ решения СЛАУ

Для решения СЛАУ матричным способом введем в рассмотрение матрицу, составленную из коэффициентов при неизвестных матpицы-столбцы неизвестных и свободных коэффициентов

Тогда СЛАУ можно записать в матричном виде Матричный способ решения СЛАУ состоит в следующем: умножим слева матричное уравнение на обратную матрицу к матрице А, получим в силу того, что произведение найдем Таким образом, для нахождения неизвестных матричным способом, надо найти обратную к А матрицу после чего надо умножить эту матрицу на матрицу-столбец свободных коэффициентов.

Пример:

Решить СЛАУ матричным способом

Решение:

Введем в рассмотрение следующие матрицы

Найдем матрицу (см. Лекцию № 2): найдем детерминант матрицы А.

Пример:

Решение:

Найдем алгебраические дополнения всех элементов Запишем обратную матрицу (в правильности нахождения обратной матрицы убедиться самостоятельно). Подействуем пай денной матрицей на матрицу-столбец свободных коэффициентов В:

Отсюда находим, что х = 1; y = l; z = l.

Метод Гаусса

Метод Гаусса или метод исключения неизвестных состоит в том, чтобы за счет элементарных преобразований привести СЛАУ к треугольному виду. Покажем использование расширенной матрицы, составленной из коэффициентов при неизвестных и расширенной за счет столбца свободных коэффициентов, для приведения СЛАУ к треугольному виду на примере системы, рассматриваемой в этой лекции. Расширенная матрица для СЛАУ имеет вид:

Замечание: В методе Гаусса желательно, чтобы первая строка расширенной матрицы начиналась с единицы.

Обменяем в расширенной матрице первую и вторую строки местами, получим Приведем матрицу к треугольному виду, выполнив следующие преобразования: умножим элементы первой строки на (-2) и прибавим к соответствующим элементам второй строки Разделим все элементы второй строки на (-5), получим эквивалентную матрицу

Умножим элементы первой строки на (—1) и прибавим к соответствующим элементам третьей строки Разделим все элементы третьей строки на (-3), получим Таким образом, эквивалентная СЛАУ имеет вид (напомним, что первый столбец это коэффициенты при неизвестной х, второй — при неизвестной у, третий — при неизвестной z, а за вертикальной чертой находится столбец свободных коэффициентов):

Из первого уравнения находим, что х = 1.

Вывод: Из вышеизложенного материала следует, что вне зависимости от

способа решения СЛАУ всегда должен получаться один и тот же ответ.

Замечание: После нахождения решения СЛАУ надо обязательно выполнить проверку, то есть подставить полученные значения неизвестных в заданную СЛАУ и убедиться в тождественности левой части всех равенств системы соответствующим правым частям. Отметим, что задание СЛАУ всегда верно, то есть, если проверка показывает нарушение оговоренной тождественности, то надо искать ошибку в проведенных вычислениях.

Ранг матрицы. Теорема Кронекера-Капелли

Определение: Рангом матрицы называется наивысший порядок отличного от нуля минора этой матрицы.

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

При вычислении ранга необходимо начинать вычислять миноры 2 порядка, затем миноры 3 порядка и так далее, пока не будут найдены миноры, обращающиеся в нуль. Если все миноры порядка p равны нулю, то и все миноры, порядок которых больше p, равны нулю.

Пример:

Найти ранг матрицы

Решение:

Очевидно, что среди миноров второго порядка есть миноры отличные от нуля, например, среди миноров третьего порядка также есть миноры, которые не равны нулю, например, Очевидно, что определитель четвертого порядка равен нулю, так как он будет содержать строку, состоящую из одних нулей (см. свойство для определителей). Следовательно, ранг матрицы А равен 3.

Теорема Кронекера-Капелли (критерий совместности СЛАУ). Для совместности системы линейных алгебраических уравнений (СЛАУ) необходимо и достаточно, чтобы ранг расширенной матрицы совпадал с рангом основной матрицы, составленной из коэффициентов при неизвестных величинах.

Следствия из теоремы Кронекера — Капелли

Следствие: Если ранг матрицы совместной системы равен числу неизвестных, то система имеет единственное решение (то есть она определенная).

Следствие: Если ранг матрицы совместной системы меньше числа неизвестных, то система имеет бесчисленное множество решений (т.е. она неопределенная).

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

Рекомендую подробно изучить предметы:

Математика
Алгебра
Линейная алгебра
Векторная алгебра
Высшая математика
Дискретная математика
Математический анализ
Математическая логика

Ещё лекции с примерами решения и объяснением:

Скалярное произведение и его свойства
Векторное и смешанное произведения векторов
Преобразования декартовой системы координат
Бесконечно малые и бесконечно большие функции
Критерий совместности Кронекера-Капелли
Формулы Крамера
Матричный метод
Экстремум функции

При копировании любых материалов с сайта evkova.org обязательна активная ссылка на сайт www.evkova.org

Сайт создан коллективом преподавателей на некоммерческой основе для дополнительного образования молодежи

Сайт пишется, поддерживается и управляется коллективом преподавателей

Whatsapp и логотип whatsapp являются товарными знаками корпорации WhatsApp LLC.

Cайт носит информационный характер и ни при каких условиях не является публичной офертой, которая определяется положениями статьи 437 Гражданского кодекса РФ. Анна Евкова не оказывает никаких услуг.

Устойчивость решения СЛАУ относительно исходных данных

(или обусловленность задач и вычислений)

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

Будем считать, что det A ¹ 0, .

Матрица А и вектор правой части во многих случаях задаются приближенно. Они получены либо в процессе эксперимента, либо в процессе каких-то промежуточных расчетов, содержащих соответственно погрешности эксперимента либо погрешности округления.

Естественно встает вопрос, как эти погрешности (возмущения) исходных данных влияют на точность решения. Чтобы на него ответить, надо познакомиться с особой характеристикой матриц, которую называют обусловленностью [3].

G Говорят, что задача, модель или вычисление плохо обусловлены, если они чувствительны к малым изменениям (возмущениям) входящих в нее величин, т.е. исходных данных. В противном случае – хорошо обусловлена.

Таким образом, обусловленность характеризует устойчивость решения системы относительно исходных данных

Введем еще одно определение: задача решения СЛАУ является корректной, если решение существует, единственно (detA¹0) и непрерывно зависит от исходных данных (матриц А и В), т.е. малым изменениям исходных данных соответствуют малые изменения решения задачи.

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

Если задача плохо обусловлена, то никакие усилия, потраченные на организацию изощренных вычислений, не могут дать правильный ответ, исключая случайность. С плохо обусловленными задачами можно столкнуться при расчетах стержневых систем методами строительной механики, например,

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

Все плохо обусловленные вычисления являются результатом применения численно неустойчивых алгоритмов. Например, метод исключения Гаусса без выбора главного элемента может обладать таким недостатком.

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

n Пример 3.7.Рассмотримплохо обусловленнуюсистему, записанную в матричном виде:

Если изменить правые части на 0,1 и принять их равными

то получим решение .

Если принять величину 1-го коэффициента в 1-ом уравнении равной 4,99 вместо 5, то получим решение .

Существенно изменится при этом и обратная матрица.

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

Обусловленность матрицы (системы) является качественной характеристикой, хотя мы будем стараться оценить ее количественно. Существует несколько способов оценки обусловленности.

Например, обусловленность матрицы (системы) можно оценить с помощью величины, называемой мерой обусловленности m(A):

где – норма матрицы А; – норма обратной матрицы.

Число m(A), часто обозначаемое cond A (от английского слова conditioned — «обусловленный»), служит также коэффициентом роста относительных погрешностей при неточном задании элементов матрицы А.

Чем больше m(A) ,тем сильнее сказываются возмущения в исходных данных на решении системы линейных уравнений. Если число m(A) велико, то система считается плохо обусловленной. Говорить о том, «что такое хорошо, а что такое плохо» в отрыве от контекста решаемой задачи почти бессмысленно, так как здесь могут играть роль размерность задачи, точность, с которой должно быть найдено ее решение, точность представления чисел в ЭВМ и т.п. Однако можно дать оценку снизу меры обусловленности. Число обусловленности m(A) не может быть меньше 1. Матрица, а соответственно и система, будет хорошо обусловленной, если m(A) стремится к единице.

n Пример 3.8. Оценим обусловленность матриц А и В:

A =

Решение:

Обратные матрицы равны:

Вычислим меры обусловленности. Для этого найдем нормы матрицы А:

Мера обусловленности m(A) = 12´0,292=4,506 невелика и матрица А хорошо обусловлена.

Нормы матрицы В:

Мера обусловленности m(B) = 21´8421=176841 очень большая и матрица Вплохо обусловлена.

Примеры решения СЛАУ с использованием электронных таблиц MS Excel

Реализация метода Гаусса

Рассмотрим решение системы линейных алгебраических уравнений (пример 3.1) методом Гаусса, используя таблицы Excel.

Последовательность действий

Введем расширенную матрицу системы, как показано на рис.3.3, в ячейки А3:D5.

Рис.3.3. Реализация метода Гаусса в MS Excel

Прямой ход метода Гаусса.

1. Поделим элементы 1-ой строки на а_{11 .}Для этого в ячейку А7 введем формулу

и скопируем ее вправо до конца строки.

2. Умножим элементы 1-ой строки на (–а₂₁ ) и прибавим ко 2-й строке. Для этого введем формулу

и скопируем ее вправо до конца строки.

3. Умножим элементы 1-ой строки на (–а₃₁ ) и прибавим к 3-й строке. Для этого введем формулу

и скопируем ее вправо до конца строки.

Таким образом исключили неизвестное х₁ из 2-го и 3-го уравнений системы (смотри 1-й шаг рис.3.3).

Осталось исключить неизвестное х₂ из 3-го уравнения системы. Для этого реализуем описанный выше алгоритм для 2-й и 3-й строк (смотри 2-й шаг рис.3.3).

На этом прямой ход метода Гаусс закончен, матрица системы приведена к треугольному виду.

Обратный ход метода Гаусса.

Найдем последовательно неизвестные, начиная с последней строки. Для этого в ячейки G12:G14 запишем формулы:

G3=D12-C12*G4 (для вычисления x₂);

G2=D11-C11*G4-B11*G3 (для вычисления x₁).

Число обусловленности матрицы и оценки погрешности решения систем линейных алгебраических уравнений

Число обусловленности матрицы и оценки погрешности решения систем линейных алгебраических уравнений — раздел Философия, Численные методы линейной алгебры Компьютерные Вычисления Являются Приближенными В Силу Того, Что Действительны.

Компьютерные вычисления являются приближенными в силу того, что действительные числа представляются конечным числом десятичных разрядов. Относительная погрешность представления действительных чисел в формате double составляет приблизительно . Естественно, что и результат арифметических операций с такими числами также будет приближенным. При решении систем линейных алгебраических уравнений число арифметических операций по порядку величины составляет величину . В силу этого анализ ошибки каждой из операций представляется практически не осуществимой задачей. По этой причине для оценки погрешности используют подход, получивший название метод обратного распространения ошибки. Суть данного метода состоит не в подсчете реальной погрешности вычисленного решения, а в выяснении того факта какая задача решена фактически. Например, пусть при решении задачи получено приближенное решение , с неизвестной погрешностью . Подстановка полученного решения в исходное уравнение показывает, что появление погрешности можно связать с возмущениями правой части задачи

Таким образом, в условиях приближенности вычислений вместо исходной системы уравнений фактически решается некоторая возмущенная задача, точное решение которой и является приближенным решением, полученным в процессе вычислений. Рассмотрим, как возмущения правой части системы ЛАУ связаны с погрешностью ее решения при условии, что все промежуточные вычисления выполняются точно.

Итак, пусть правая часть системы возмущена – задана с абсолютной погрешностью . В силу этого фактически вместо задачи мы решаем возмущенную задачу

. (2.17)

где – абсолютная погрешность решения, ассоциированная с возмущением правой части. Погрешность является решением следующей задачи:

. (2.18)

Несложные преобразования позволяют получить из уравнения (2.18) оценку нормы абсолютной величины погрешности:

. (2.19)

Заметим, что последнее неравенство (2.19) выражает устойчивость решения по правой части, и (согласно условию (1.15)) требование устойчивости эквивалентно требованию ограниченности нормы обратной матрицы системы ЛАУ. Из постановки задачи имеем

. (2.20)

Из неравенств (2.19) и (2.20) следует оценка относительной погрешности возмущенной задачи:

. (2.21))

Оценка (2.21) выражает зависимость относительной погрешности решения возмущенной задачи от относительной величины возмущения правой части в произвольной норме векторного пространства. В частности, согласно (2.21), погрешность возмущенной задачи пропорционально возрастает с ростом возмущений правой части, причем коэффициент пропорциональности определяется произведением норм матриц и . Число

, (2.22)

характеризующее зависимость относительной погрешности решения системы ЛАУ от величины относительного возмущения правой части, называется числом обусловленности матрицы. Если число обусловленности матрицы велико, то говорят, что данная матрица плохо обусловлена. Если число обусловленности близко к единице, то матрица считается хорошо обусловленной. Обычно для оценки числа обусловленности используется спектральная норма матриц, которая является подчиненной для евклидовой векторной нормы. Для симметричных матриц число обусловленности определяется отношением модулей наибольшего и наименьшего собственного значения матрицы.

Плохая обусловленность матрицы системы ЛАУ характеризует сильную чувствительность решения задачи к погрешности входных данных (малая ошибка входных данных приводит к существенному изменению решения). Аналогичным образом плохо обусловленные системы ЛАУ реагируют и на погрешности промежуточных вычислений. Так, например, в процессе приведения матрицы системы к треугольному виду выполняется ряд преобразований ее коэффициентов. В итоге, на этапе обратного хода метода Гаусса решается задача с возмущенными коэффициентами матрицы и полная оценка относительной погрешности должна исходить из следующей возмущенной задачи:

., (2.23)

Если матрица возмущенной задачи (2.23) не вырожденная, то возмущения коэффициентов матрицы могут быть соотнесены с возмущениями правой части и вместо задачи (2.23) достаточно рассмотреть задачу

, (2.24)

для которой имеет место оценка (2.21). На практике величина может быть вычислена на основе полученного приближенного решения задачи :

. (2.25)

Вектор принято называть невязкой решения системы ЛАУ. Норма данного вектора на практике служит количественной мерой возмущения правой части задачи и используется для оценки погрешности приближенного решения.

Оценки числа обусловленности матриц требуют вычисления обратной матрицы или, по крайней мере, оценки максимального и минимального собственных значений в случае симметричных матриц. В силу этого практическая оценка фактической точности приближенного решения системы ЛАУ согласно неравенству (2.21) представляет собой сложную задачу. Тем не менее, для ряда практически значимых случаев оценка (2.21) представляется полезной в плане контроля точности вычислений.

1. Доказать, что число обусловленности матрицы не меньше единицы

источники:

http://lektsia.com/6x31e9.html

http://allrefs.net/c1/48zvh/p7/

Источник

Добрый вечер всем. Есть СЛАУ — 4 неизвестных, 4 уравнения, которую необходимо решить и оценить погрешность решения. Решить я ее кое-как решил, но вот на оценке погрешности я повис. Задание звучит так: «Определить число обусловленности и оценки сверху погрешности решения СЛАУ». Обусловленность я посчитал, система хорошо обусловлена. Формулы абсолютной (Δх=х-а) и относительной (δх=Δха) погрешностей мне известны, но возник вопрос, как их правильно применить. Я получил точное решение методом Гаусса (до 9 знака все сходится). И есть решения методами Холесского и Зейделя. Там ответы немного не совпадают, сказываются ошибки округления, по заданию точность до 10^-3. Подскажите, как правильно подставить в формулы имеющиеся у меня числа. И возможна ли оценка погрешности решения не зная точного ответа?

Добавлено через 8 часов 1 минуту
Полистав литературу, вроде понял принцип расчетов. Поправьте, если я не то считаю, что надо.
СЛАУ можно рассматривать как систему функций 4-х переменных. Взяв одно из уравнений и обозначив его как f(x1,x2,x3,x4). Соответственно, абсолютную погрешность этой функции можно рассчитывать как приращение функции, следовательно как ее дифференциал вида Δu=|f'(x1,x2,x3,x4)|Δx1 + |f'(…)|Δx2 + |f'(…)|Δx3 + |f'(…)|Δx4.

Относительную погрешность рассчитаем тогда по формуле δu=Δu/|f(x1,x2,x3,x4)|, а в качестве численного значения функции будем использовать тождество, в которое обратится мое уравнение при подстановке вектора неизвестных.
Воистину так, или ерунду написал?

__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь

Источник

Предположим, что матрица и правая часть системы заданы неточно и вместо предъявленной к решению системы

в действительности должна была решаться некоторая система

Пусть известны оценки и . Займемся оценкой погрешности решения.

Сначала выделим главный член погрешности. Будем обозначать решения (1) и (2) через X и и разность — через . Подставив выражения в (2), будем иметь

Вычитая из этого равенства (1), получим

откуда

Если и малы, то следует ожидать и малости . Тогда слагаемое имеет более высокий порядок малости; отбрасывая слагаемое, получаем

Отсюда следует оценка погрешности

(4)

Строгая оценка погрешности получается следующим образом. Вследствие (3) выполняется неравенство

Предположим, что . Перенеся последнее слагаемое в левую часть и поделив неравенство на коэффициент при , получим оценку

Довольно распространен случай, когда погрешность матрицы системы существенно меньше погрешности правой части. В качестве модели этой ситуации будем рассматривать случай точного задания матрицы системы. Тогда, полагая в , имеем

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

Соответственно этому в качестве меры обусловленности системы принимается число

Отсюда получаем оценку относительной погрешности решения через меру обусловленности системы и относительную погрешность правой части:

Так как , то

Иногда удобнее иметь более грубую характеристику свойств системы только через свойства матрицы А. Эту характеристику называют мерой (или числом) обусловленности матрицы А. Согласно этому определению и (6), имеем оценку

связывающую относительные погрешности правой части и решения только через свойства матрицы системы. Так как

то

Поскольку любая норма матрицы не меньше ее наибольшего по модулю собственного значения, то поскольку собственные значения матриц А и взаимно обратны, то

Таким образом,

В частности, при имеем и

Следовательно, в случае нормы

Рассмотрим вопрос о погрешности решения вследствие округления в ЭВМ правой части. Пусть, как обычно, t -двоичная разрядность чисел в ЭВМ. Каждый элемент правой части округляется с относительной погрешностью , т.е. с абсолютной погрешностью, равной , поэтому

Следовательно,

При практической работе вопрос: о строгой оценке погрешности полученного приближенного решения системы линейных уравнений с помощью полученных неравенств или каким-либо иным способом возникает редко. Однако информация о порядке погрешности решения часто полезна для получения качественных выводов о том, с какой точностью разумно решать задачу. Соотношения (4), (5) оценивают сверху погрешность решения, являющуюся следствием погрешности исходных данных. Из равенства (3) видно, что оценки (4), (5) довольно точны, поэтому обычно не имеет смысла стремиться получать решение задачи с погрешностью, существенно меньшей чем .

Системы уравнений и матрицы с большими значениями мер обусловленности принято называть плохо обусловленными, а с малыми — хорошо обусловленными. Если правая часть (4), оценивающая погрешность решения через погрешность исходных данных, или оценка вычислительной погрешности недопустимо велики, то полезно принять во внимание какую-то дополнительную информацию о решении рассматриваемой задачи. Подход к решению такой задачи должен быть таким же, как в случае некорректных задач.

Рассмотрим простейший случай, когда А — симметричная матрица. Пусть — ее собственные значения, упорядоченные в порядке убывания соответствующую ортонормированную систему собственных векторов обозначим через . Решением системы является вектор

При реально заданной правой части решением будет

Коэффициент может оказаться очень большим при малых , что ведет к сильному искажению решения. Иногда заранее известно, что в разложении искомого решения задачи коэффициенты , соответствующие малым по модулю , малы. В этом случае следует принять какие-то меры с тем, чтобы «отфильтровать» эти составляющие решения.

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

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

Первый способ. Задавая некоторое , находим решение системы

записывается в виде

Так как

то наличие малого параметра а несущественно изменит слагаемые, соответствующие большим . В то же время при имеем

Это означает, что введение параметра приводит к существенному уменьшению роли слагаемых, соответствующих малым . Подбор оптимального значения обычно осуществляют экспериментально, сравнивая результаты расчетов при различных .

Второй способ заключается в следующем. Будем решать систему уравнений каким-либо итерационным способом. Рассмотрим случай итераций по формуле

при некотором начальном приближении . Пусть

Подставим эти выражения в (7) и, приравнивая коэффициенты при , получим соотношения

Последовательно выражая каждое через предыдущие, имеем

Если , то при

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

В других случаях решение задачи находят, минимизируя некоторый функционал, близкий к , например функционал с малым .

Успешность применения описанных приемов в случае несимметричных матриц А в существенной степени зависит от структуры жордановой формы и от ряда свойств матрицы. Здесь часто решение находят, минимизируя функционал

при малых значение опять-таки подбирается экспериментально из сравнения результатов расчетов при различных .

Другая группа методов основана на представлении матрицы системы А в виде

где G и Р — ортогональные матрицы, а — двухдиагональная матрица, у которой могут быть отличными от нуля элементы при и .

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

Задача 1. Пусть — матрица размерности с элементами

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

2. Выписать явно решение системы через правую часть.

3. Выписать явно через правую часть вектор , минимизирующий функционал

4. Попытаться качественно описать эффект, достигаемый за счет применения такой регуляризации.

Объясним еще одну причину, по которой стараются избегать симметризации матриц, предложенной в § 6. Сначала посмотрим, что происходит, когда операция симметризации применяется формально в случае симметричной матрицы. Тогда и . При возведении матрицы в квадрат собственные значения возводятся в квадрат, поэтому при имеем

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

Задача 2. Существуют ли несимметричные матрицы, для которых .

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

Относительно А будем считать, что в спектре матрицы есть как собственные числа порядка 1, так и собственные числа, близкие (или даже равные) к нулю. Это как раз и означает, что матрица А плохо обусловлена.

Заметим, что в силу наших предположений относительно собственных значений матрицы , часть из них может быть равна нулю. Таким образом, уравнение (8), вообще говоря, может не иметь решения в классическом смысле.

Назовем решением X уравнения (8) вектор, который минимизирует функционал невязки, а именно,

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

Уравнение (10), в отличие от (8), всегда имеет решение. Действительно, непосредственной проверкой убеждаемся, что . Необходимым и достаточным условием существования решения линейной системы уравнений (10) является ортогональность правой части ядру матрицы системы, т.е. вектор должен быть ортогонален ядру , которое, как мы отметили выше, совпадает с ядром . Но из вида правой части видно, что она действительно ортогональна ядру А. Таким образом, система (10) всегда имеет решение. В общем случае таких решений может быть несколько.

Описываемый ниже метод заключается в минимизации функционала методом оптимального покоординатного спуска; на каждом шаге выбирается координата, спуск по которой будет оптимальным в смысле минимизации . В качестве координатных (базисных) векторов можно выбрать любую ортонормированную систему.

Пусть — ортонормированная система векторов в (не обязательно базис) и по крайней мере для одного из векторов. Обозначим через W линейную оболочку векторов . Будем искать вектор, минимизирующий функционал невязки на подпространстве W. Для этого рассмотрим следующий итерационный метод. Положим

Если приближение уже найдено, то следующее приближение будем искать в виде , где

(11)

Наряду с приближениями введем невязки

Выпишем условия минимума функционала по . Имеем

Заметим, что при поиске минимума достаточно рассматривать только те , для которых так как в противном случае значение функционала не меняется. Функция , как функция переменной , является многочленом второй степени, причем коэффициент при положителен в силу замечания выше. Отсюда следует, что минимум по при фиксированном j существует и единствен, если Таким образом, из (13) следует, что удовлетворяет уравнению

откуда

При таком выборе

Суммируя вышесказанное, получаем следующий алгоритм:

1) Вычисляем векторы , и их нормы в дальнейшем рассматриваем только те векторы , для которых . Не уменьшая общности, будем считать, что число таких векторов равно .

2) Выбираем на основе априорной информации; в частности, можно взять .

3) Если найден, то вычисляем по формулам

(14)

4) Следующее приближение вычисляем по формуле

Найдем трудоемкость метода. Для этого оценим число арифметических операций на шаге. Прежде всего заметим, что предварительные операции (этап 1) требуют в общем случае операций.

Этап 3 итерационного метода требует , а этап 4 — арифметических операций.

Таким образом, общая трудоемкость метода составляет арифметических операций, где — число шагов итерационного процесса.

Отметим также, что из (14) находится в общем случае неоднозначно (таких индексов может быть несколько). В этом случае в качестве можно брать, например, наименьший.

Исследуем сходимость итерационного метода. Имеет место

Лемма. Пусть — произвольный набор линейно независимых единичных векторов из линейная оболочка этих векторов. Тогда существует , такое, что для любого справедливо неравенство

Доказательство. Положим

Покажем, что функционал непрерывен. Для этого достаточно показать непрерывность функционала , где определено выше. Рассмотрим разность , где индекс определен выше, а — индекс, определяемый аналогичным образом для .

Пусть для определенности . Тогда справедлива цепочка неравенств

откуда и следует непрерывность рассматриваемого функционала.

Предположим, что утверждение леммы неверно. Тогда существует последовательность такая, что , где при . Так как в конечномерном пространстве сфера компактна, то существует сходящаяся подпоследовательность. Для простоты изложения предположим, что сходится сама последовательность

В силу непрерывности функционала имеем .

Следовательно, при имеем

Отсюда следует, что . Так как для любого , то при всех . Так как принадлежит линейной оболочке векторов , то последнее равенство может выполняться лишь при , что противоречит условию . Лемма доказана.

Теорема. Последовательность приближений , получаемая в ходе итерационного метода (14), (15), является фундаментальной и сходится к некоторому вектору, минимизирующему функционал невязки на подпространстве W, со скоростью геометрической прогрессии. А именно, существует такое, что

Постоянная q при этом зависит от выбора базиса и оператора А.

Доказательство. Так как , то существует постоянная такая, что

Из (14), (15) следует, что невязки удовлетворяют соотношению

Положим . Тогда (17) примет вид

Поскольку выбиралось из условия минимума , то

и мы находимся в условиях предыдущей леммы. Тогда из условий леммы следует оценка

Из (14) и (15) имеем

откуда, учитывая (16), получаем оценку

Применяя к полученному неравенству оценку (18), имеем

откуда следует цепочка соотношений

Таким образом, последовательность является фундаментальной и имеет предел . В силу построения, минимизирует функционал на подпространстве W. Теорема доказана.

Описанный выше метод решения систем уравнений с плохо обусловленными матрицами особенно эффективен в случае, когда априорная информация представлена в виде каких-либо сведений о структурных особенностях искомого решения; например, когда известны базисные функции , и решение представимо в виде разложения по небольшому числу этих функций. Такая ситуация часто имеет место в задачах цифровой обработки сигналов.

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

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