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

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

(2.5)

Теорема. Пусть правая часть и невырожденная матрица СЛАУ (2.4) вида Au = f, , получили приращения и соответственно. Пусть существует обратная матрица А –1 и выполнены условия где В этом случае оценка относительной погрешности решения удовлетворяет неравенству

Доказательство. Из (2.5) следует, что Переходя в этом равенстве к норме и использовав неравенство треугольника, получаем или

Вводя обозначение перепишем последнее равенство в виде

Заметим, что т.к. .

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

. (2.6)

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

, (2.7)

если в (2.5) положить то

. (2.8)

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

, (2.9)

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

.

При , то ошибки входных данных слабо сказываются на решении и система (2.1) считается хорошо обусловленной. При система является плохо обусловленной.

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

будет пара чисел .

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

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

, (это очень малая величина), , .

Значит , что согласуется с результатами решения возмущенной и невозмущенной задач. Для невозмущенной задачи

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

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

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

Среды прямых методов численного решения СЛАУ широко используется также LU-разложение матрицы ^ А и метод Холецкого (или метод квадратного корня).

Если матрица А представима в виде произведений матриц LU, то СЛАУ может быть представлена в виде

(2.13)

Перепишем (2.13), вводя вспомогательный вектор v, в следующем виде

(2.14)

Решение СЛАУ свелось к последовательному решению двух систем с треугольными матрицами. Первый этап решения системы Lv = f:

откуда можно вычислить все v_k последовательно по формулам

; .

Далее, рассмотрим систему Uu = v или

.

решение которой находятся в обратном порядке, т.е. при k = n – 1,…,1 по очевидным формулам

Условия существования такого разложения даются следующей теоремой [5] (без доказательства).

Теорема. Если все главные миноры квадратной матрицы ^ А отличны от нуля, то существуют единственные нижняя и верхняя треугольные матрицы L = <l_ij> и U = <d_ij> такие, что А = LU. При этом все диагональные коэффициенты матрицы L фиксированы и равны единице.

Опишем алгоритм нахождения элементов l_ij d_ij матриц L, U. Выписав равенство А = LU в компонентах, получим

Выполнив умножение матриц, приходим к системе линейных уравнений размером n  n:

Специфика этой системы позволяет решить ее последовательно. Из первой строки находим d_1j = a_1j (j = 1,…, n).

Из уравнений, входящих в первый столбец приведенной выше системы, находим l_i1 = a_i1/d₁₁, i = 1,…, n. Теперь можно из уравнений второй строки найти d_2j = a_2j – l₂₁d_1j, j = 2,…, n, а из уравнений, входящих во второй столбец, получим l_i2 = d(a_i2 – l_i1d₁₂), i = 2,…, n и так далее. Последним вычисляется элемент

Можно выписать общий вид этих формул

i  j,

i > j.

Итерационные методы решения СЛАУ

Метод простой итерации

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

Проведем несколько равносильных преобразований. Умножим обе части системы на один и тот же скалярный множитель τ, затем прибавим к правой и левой частям системы вектор u. Систему уравнений можно теперь записать в виде, удобном для итераций

Теперь построим последовательность приближений к решению системы. Выберем произвольный вектор u₀ — начальное приближение к решению. Чаще всего его просто полагают нулевым вектором. Скорее всего, начальное приближение не удовлетворяет (2.15) и, следовательно, исходной системе. При подстановке его в исходное уравнение возникает невязка r₀ = f – Au₀. Вычислив невязку, с помощью (2.15) можно уточнить приближение к решению, считая что

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

(2.16)

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

Существуют другие формы записи метода итераций, например

(2.17)

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

(2.18)

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

Теорема (достаточное условие сходимости метода простой итерации).

Итерационный процесс (2.16) сходится к решению U СЛАУ со скоростью геометрической прогрессии при выполнении условия: .

Доказательство. Пусть U — точное решение системы (2). Вычитая из (2.16)-(2.15), получим , или, обозначив погрешность , получим для эволюции погрешности уравнение Справедлива цепочка неравенств:

где

Источник

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

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

Определение. Говорят, что задача поставлена корректно, если ее решение существует, единственно и непрерывно зависит от входных данных.

Будем считать, что решение и правая часть задачи (6.1) принадлежат линейному пространству H, состоящему из N-мерных векторов. Введем в H норму, для которой выполнено:

||X||>0, для всех Х≠0H ,

||α X||=| α| ||X||, для любого числа А и ХH ,

||X+Y||≤||X||+||Y||, для любых X и YH .

Определение. Нормой матрицы А, подчиненной данной норме векторов, называется число , для всех Х≠0H .

Эта оценка выражает факт непрерывной зависимости решения от правой части, то есть показывает, что || δx|| Стремится к нулю при || δf ||Стремящемся к нулю. Наличие устойчивости очень важно при численном решении систем уравнений, так как никогда нельзя задать правую часть F точно. Погрешность δf возникает в результате округления.

.

Определение. Число ρ(A)= называется числом обусловленности матрицы A и характеризует степень зависимости относительной погрешности решения от относительной погрешности правой части. В случае самосопряженной матрицы A =A* это число равно

ρ(A)=,

Где λMax , λmin – максимальное и минимальное по модулю собственные значения матрицы A.

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

Например, для матрицы

Число обусловленности ρ(A)=, И если взять за правую часть системы вектор F= (1,0000, 1,0000)T, то получим решение X=(0,3333, 0,0000)T. Решение «возмущенной» системы с правой частью Fδ = (0,9998, 1,0000)T равно Xε=(5,0000, 2,0000)T.

Если взять матрицу

Источник

• ← для вычисления объема какого геометрического тела не потребуется число пи
• для вычисления энергии связи ядра в си в каких единицах нужно выразить значение дефекта массы →