Чувствителност на линейните уравнения

Нека да сме благодарни на проф. Михаил Константинов за разрешението да четем "Елементи на линейната алгебра: вектори и матрици" online.

В тази глава е изучена чуствителността на решението на ли-нейните алгебрични уравнения относно смущения в данните. Интуитивно, една задача е силно чуствителна, ако малки изменения в данните водят до големи изменения в резултата (тук понятията „малко" и „голямо" са в контекста на конкретната изчислителна среда). Решаването на такава задача с помощта на компютър може да е свързано с големи грешки от закръгляне.

Изучаването на чуствителността на изчислителните задачи се извършва с техниките на т.нар. пертурбационен анализ (или анализ на смущенията).

Изобщо, изследването на чуствителността на дадена задача е важно поради поне три основни причини:

•      Чуствителността е важна вътрешна характеристика на задачата и в това си качество представлява чисто теоретичен интерес.

•      Математическите модели на реалните физически явления и процеси обикновено се характеризират със структурни и параметрични неточности (или неопределености), например дължащи се на грешки от измервания. Така на практика изследователят разполага не с фиксиран модел, а със семейство от модели, зависещо от неопределеностите. Познаването на чуствителността на задачата позволява да се намерят границите, в които се намира „истинското" решение, като функция на неопределеностите в данните.

•      Когато задачата се решава в машинна аритметика с помощта на числено устойчив алгоритъм, изчисленото решение се оказва близко до точното решение на близка задача. В този случай на основа на чуствителността на задачата могат да се изведат оценки за грешката в изчисленото решение [2, 9, 8].

Горните разсъждения показват необходимостта от анализ на чуствителността на изчислителните задачи, възникващи в научната и инженерната практика.

9.1 Уравнения с неособена матрица

Навсякъде в този раздел с || • || е означена произволна норма в Fⁿ или съответната матрична норма в F^{n x n}.
Да разгледаме линейното алгебрично уравнение с квадратна неособена матрица
Ах = b,
където A F^{n x n} (det(А) ≠ 0) и b Fⁿ са данните и х Fⁿ е търсеното решение. Тъй като матрицата А е неособена, решението е единствено и може да се запише във вида
х = А^-1b.
Ще подчертаем, че това е един формален запис, от който не следва, че сме успели да пресметнем решението. Нещо повече, обикновено при намиране на решението обратната матрица изобщо не се формира (освен ако не ни е необходима за някаква друга цел).
По-нататък ще предполагаме, че b ≠ 0, откъдето х ≠ 0.
Да предположим, че данните са подложени на смущения
А → А + δА, b → b + δb,
където смущението δА е толкова малко, че
||А^-1||.||δА|| < 1.
Последното неравенство гарантира неособеност на смутената матрица А + δА. Да означим с х + δх решението на смутеното уравнение с данни А + δА, b + δb, т.е.,
(А + δА)(х + δх) = b + δb.
Нашата цел ще бъде да намерим оценка за относителното изменение в решението
δ_x := ||δ_x||/||x||
като функция на относителните изменения в данните
δ_A := ||δ_A||/||A||, δ_b := ||δ_b||/||b||
Важна роля в тези оценки играе т.нар. относително число на обусловеност на матрицата А относно обръщане, което се дефинира като
c_A = cond(A) := ||A||.||A^-1||.
Числото на обусловеност се дефинира и за произволна матрица А (не непременно квадратна, но от пълен ранг) както следва
където А* е псевдообратната матрица на матрицата А (глава 13).
С отчитане на равенството Ах = b от смутеното уравнение следва
Аδх + δАх + δАδх = δb
и
δх = А^-1δb - А^-1δАх - А^-1δАδх.
Оттук
(9.1)          ||δ_x ≤ ||A^-1δb|| + ||A^-1δAx|| + ||A^-1δAδx|| ≤ ||A^-1||.||δb|| + ||A^-1||.||δA||.||x|| + ||A^-1||.||δA||.||δx||.
Да положим
γ = γ(A, b) := ||b||/||A||.||x|| = ||b||/||A||.||A^-1b||
Tъй като ||b|| ≤ ||А||.||x||, то γ ≤ 1. От друга страна
γ = ||b||/||A||.||A^-1b|| ≥ ||b||/||A||.||A^-1||.||b|| = 1/c_A.
Tака за величината γ имаме оценките
1/c_A ≤ γ ≤ 1,
които са достижими.
Разделяме двете страни на неравенството (9.1) с ||x|| с отчитане на направените полагания и получаваме
δ_x ≤ ||A||^-1||.||A||γδ + ||A^-1||.||δA|| + ||A^-1||.||δA||δ_x = c_Aγδ + c_Aδ_A + c_Aδ_Aδ_x.
Тъй като по предположение с_Аδ_А < 1, то окончателно получаваме

Ако относителните смущения δ_b, δ_A в данните са ограничени от някаква достатъчно малка константа η (в практическите пресмятания η е от порядъка на мярката на закръгляне ерs на машинната аритметика), то
δ_x ≤ (1 + γ)с_Aη + O(η²) ≤ 2с_Аη + O(η²),
където с O(η²) са означени малките от втори и по-висок ред относно η. Така величините (1 + γ)c_А или 2c_A могат да се приемат като относителни числа на обусловеност на задачата за решаване на линейно алгебрично уравнение с неособена матрица А.

9.2 Точност на решението

Има едно полезно евристично правило за приблизително определяне на броя на верните значещи цифри в решението на уравнението Ах = b с неособена матрица А, изчислено в машинна аритметика с мярка на закръгляне ерs (обикновено ерs ≈ 10^-16). Преди всичко необходимо е да е изпълнено неравенството
с_Aерs < 1
(в противен случай в решението може да няма вярна значеща цифра), а е желателно да имаме даже
с_Aерs << 1.
В този случай може да се очаква, че в изчисленото решение х ще има около
-log₁₀(с_Aерs)
верни значещи десетични цифри.

Практиката е показала, че за умерено голям размер n на матрицата А F^nxn в уравнението Ах = b и при използване на метода на Гаус, абсолютната грешка в изчисленото решение може да се оцени от
||х — х^{^}||₁ ≤ ерsn²c_1,A||x^{^}||₁,
където
c_1,A :=||A||₁||A^-1||₁.
При използване на QR декомпозицията А = QR на матрицата А за решаване на уравнението Ах = b чрез обратно заместване, съответната грешка е
||х - х^{^}|| ≤ 10epsn^1,5c_A, с_А = ||А|| ||А^-1||.
Понякога е необходимо решението да се получи с много голяма точност, например търси се решение x^≈, приблизително равно на най-близкия до точното решение х машинен вектор. За целта се използва итерационно уточняване на решението х^{^}, получено по метода на Гаус или по метода на QR декомпозицията.

Да означим х⁽¹⁾ = х^{^}. Тогава абсолютната грешка δ⁽¹⁾ := х — х⁽¹⁾ удовлетворява уравнението
Aδ⁽¹⁾ = г⁽¹⁾,
където г⁽¹⁾ := b — Ах⁽¹⁾. Пресметнатото на свой ред решение δ^{^(1)} се използва за уточнаване на решението по формулата
x⁽²⁾ := x⁽¹⁾ + δ^{^(1)},
като x⁽²⁾ е по принцип по-добро приближение към точното решение х в сравнение с x⁽¹⁾.

Този процес на построяване на последователни приближения х^(к) към х продължава докато от някое р нататък последователните приближения започнат да осцилират в относителна ерs-околност на х^{^(p)}. Векторът х^{^(p)} обикновено е в относителна ерs-околност на точното решение.

9.3 Задача за най-малки квадрати

В този раздел с || • || е означена 2-нормата в Fⁿ или вF^nxn. Да разгледаме задачата за най-малки квадрати (ЗНМК)
Ах ≅ b,
където А F^mxn и b F^m са данните, образуващи един m(n + 1)-мерен вектор, чиито елементи са елементите на А и b. Търси се решение х Fⁿ с минимална норма ||x||, което минимизира нормата ||Ах — b|| на остатъчния вектор Ах — b. Така х е решение на оптимизационната задача
||Ах — b|| → min,
||x|| → min.
Да означим с r ≤ min{m, n} ранга на матрицата А и нека
σ₁ ≥ .... ≥ σ_r
са положителните сингулярни стойности на А (глава 13). Ще разглеждаме само интересния случай А ≠ 0 и b ≠ 0, когато решението х на ЗНМК е различно от нула. Действително, ако А = 0 или b = 0, то ЗНМК има тривиално решение х = 0.

Ще напомним, че задачата за минимизиране само на величината ||Ах — b|| има единствено решение х точно когато r = n. В този случай няма защо да минимизираме нормата ||x||. Ако обаче r < n, то векторите, които минимизират ||Ах — b||, образуват (n — r)-мерно линейно многообразие с направляващо подпространство Кеr(А). Тогава именно допълнителното изискване ||x|| → min! води до единственост на решениете.
Нека δА и δb са смущения в А и b и
δ_A = ||δА||/||A||, δ_b = ||δb||/||b||.
Ще предполагаме, че за смущението δА е в сила неравенството
||А^t|| ||δА|| = ||А|| ||А^t||.(||δA||/||A||) = с_Aδ_A = (σ₁/σ_r)δ_A < 1
и
rank(A + δА) ≤ r.
Според последното неравенство смущението δА е структурирано така, че не се допуска нарастване на ранга на смутената матрица А + δА в сравнение с този на А. От друга страна неравенството с_Aδ_A < 1 гарантира, че рангът на А + δА не е по-малък от този на А. Така че двете неравенства за δА фактически означават, че rank(А + δА) = r. Последното равенство за съжаление не може да се избегне, защото ако се окаже, че rank(A + δА) > r, то смущението в решението на ЗНМК не може да се оцени разумно отгоре.

Нека х + δх е решението на смутената ЗНМК с данни А + δА, b + δb. Тогава за относителното смущение
δ_x = ||δx||/||x||
в решението е в сила оценката
δ_x ≤ k_Аδ_А + k_bδ_b,
където

Тази оценка е в сила в общия случай, при всякакви съотношения между числата m, n и r. В този смисъл тя е и песимистична. При определени съотношения между горните три числа, например когато матрицата А е от пълен ранг r = min{m, n}, оценката може да се подобри.

Случаят m = n = r вече беше разгледан в предишния раздел.

Да разгледаме останалите два основни подслучая, когато матрицата А е правоъгълна и от пълен ранг.
В най-важния за практиката случай на ЗНМК с r = n < m е достатъчно да поискаме само изпълнение на неравенството с_Аδ_А < 1, тъй като тогава автоматически имаме rank(А + δА) = г. Тук имаме оценката
δ_x ≤ k_Аδ_А + k_bδ_b,

където
Да разгледаме накрая случая r = m < b. В сила е оценката δ_x ≤ k_Аδ_А + k_bδ_b, където
k_A := √2,k_b := c_A/1 - c_Aδ_A.

9.4 Упражнения

Упражнение 9.1 Формирайте множества от (псевдо)случайни квадратни и правоъгълни матрици и пресметнете числата им на обусловеност в матричната норма || • ||_F и операторните норми ||&bul;;||_р,р = 1,2,∞. За целта използвайте диалоговите системи SYSLAB или МАТLАВ, вж. [10].

Упражнение 9.2 Формирайте матрицата на Хилберт Н = [h_i,j] R^nxn с елементи. Изследвайте числото на обусловеност на Н като функция на реда n на матрицата.

Изпратете материали(програми), свързани с математика на: