Босс В. - Лекции по математике Том 3. Линейная алгебра, страница 30

р«заел 2.Ь Глава 10. Численные методы 184 Так или иначе, становится ясно, что для овладения ситуацией в целом нс обходимо близкое знакомство с матрицей А. Проникновение в ее внутреннес устройство, понимание, как различные коэффициенты влияют на интегральные свойства системы. Матрица затрат задается ведь не на небесах, а зависит от используемых технологических процессов, потерь от неорганизованности и т, и Поэтому в окрестности решаемых задач всегда маячат проблемы другого уровня Как перестроить систему? На чем сосредоточить внимание, ресурсы? Так что вычислительная практика — это совсем другая епархия.

Теоретические акценты очень сильно меняются. Простейшая задача решения системы Ах = Ь, например, сама по себе обычно не интересует, хотя иногда так кажется. Причина довольно проста. Когда порядок системы, скажем, всего 1О х 1О, но от записи матрицы уже рябит в глазах, голому решению едва ли кто обрадуется. поскольку голое решение — кот в мешке' ). Хотя бы потому, что матрица может быть близка к вырожденной.

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

Потом без 5) математики не обойдешься, но важно, чтобы решались эааачи «те, чю нужно», а не взятые с потолка' ). На практике в 99% случаев решается «лишь бы что» Но это нормально. Так устроена природа. Из миллионов сперматозоидов, двигаюшихся «лишь бы куда», один попадает в цель — и для поддержания интереса к численным методам этого оказывается достаточно. 10.2. Ошибки счета и обусловленности В принципе ясно, что практическое решение систем уравнений Ах = 6 сталкивается с трудностями, если матрица А близка к вы- 4) Особенно, если размер матрицы !О х !О и в глазах не рябит, потому что никому 4 в пиову не придет выводить такую матрицу на бумагу из памяти.

5) Люди, которые могут разобраться н поставить задачу — товар штучный, большая редкость. 6) Разумеется, только в сказке ситуация аккуратно делится на два этапа: постановка, потом решение. Реально все переплетено и перепутано. Поэтому нужна здравая направляющая )зуюь 10.2. Ошибки счета и обусловленность 185 рожденной. Но что значит «близка»? До сих пор фигурировали черно-белые тона «вырождена — не вырождена». Каким параметром можно характеризовать нейтральную полосу? !099 1 Матрица [ ' ! ~ «плоха», потому что изменение ее элементов на 1% может увести решение Ах = Ь в бесконечность.

Ее детерминант близок к нулю, де! А = !О 4, — но служит ли это индикатором? Не служит. Потому что у мат- Гоо! о ! рицы [ О 1! детерминант такой же, но это «хорошая» матрица, потому что изменение ее элементов на ! % дает в решении относительную ошибку того же порядка. Скрытый механизм определяется числом вбусловвеллости. Априорная оценка. Пусть Ах = Ь и А(х+ гдх) = Ь+ хдЬ, где хз х — смешение решения Ах = Ь при возмущении правой части иа хзЬ. Под возмущением исходных данных может подразумеваться что угодно.

Ошибки при физическом измерении параметров, неточный прогноз, ошибки счета и округления. < Очевидно, !!Ь|! = !)Ах(! ( ((А!! ()х!Ь !(йх(! = !1А 'бхЬ!! ( !!А '(!. !!бгЬ!!, откуда Пусть теперь Ах = д и (А+ г!ьА)(х+ хзх) = Ь, где Агх по-прежнему смещение решения Ах = Ь, но уже прн возмущении матрицы на гдА. Аналогично предыдушему !!бхх(! = |!А ~гзА(х+ сзх)!! ( !!А ~!!. !!АА!! !!х+ Гзх!!, откуда Глава 10. Числвнныв методы 186 В том и другом случае определяющую роль играет величина называемая числом обусловленности т>. В случае вырожденной матрицы полагают ет(А) = оо. Для невырожденной матрицы и евклидовой нормы, в(А) = —, а,(А) ан(А)' где а1(А) — максимальное сингулярное число, ан(А) — минимальное.

Для симметричной матрицы 1Л, (АЯ ( ) !Л„(АИ' где собственные значения Л,,..., Л„расположены в порядке убывания модулей. Число обусловленности всегда >1, поскольку .Г= АА ' =ь 1= йАА '((<!)Ай 'йА 'й =в(А). Чем о'(А) больше, тем хуже оценки. В этом случае говорят о ллохой обусловленности матрицы. Роль понятия обусловленности матрицы рассмотренными задачами не исчерпывается. Апостериорная оценка. Приведенные выше оценки решения опирались только на информацию о возмушениях АА, ЬЬ. Подход может быть иной. Уравнение Ах = Ь так или иначе приближенно решается, что дает Ах' в Ь.

Далее вывод о близости в' к настояшему решению х делается на основе вектора невязки д = Ах' — д . В силу йЬЬ = 'ЬАха ( )(АЬ 'ах~! и А 'в = х' - А 'Ь = х - х', имеем йхй > —, !!х — х'!! ~<!!А 'и ° ~!б~1 )(Ь!! ~ Термин введен Тьюрннгом. 10.3. Оценки сверлу и ло вероятности 1В7 Деление второго неравенспш на первое приводит к 10.3. Оценки сверху и по вероятности Оценки предыдущего раздела — это оценки сверху, дающие максимально пессимистический прогноз. Реальные ошибки могут быть меньше. Не в нашей Вселенной, правда.

У нас бутерброд падает маслом вниз, и вообще, всякая потенциальная неприятность случается. Подтверждением тому в данном контексте служит ряд работ, где устанавливается, что вероятные ошибки в естественных предположениях близки к наихудшим аз. Воронка неприятностей, получается, затягивает. вот простые наводящие соображения из [18[. если матрица А с нормой порядка единицы плохо обусловлена, то в А ' = [а';.[ обязательно найдугся большие элементы«1. Дифференцируя я = А 'Ь = [ац[Ь по Ьз, получаем дяв откупа ясен источник происхождения больших ошибок «Зяв а' «Ьу Что касается возмущений самой матрицы А, то заесь «возни«чузь больше Дифференцирование тождеств Е У аоа„= ба приводит к соотношениям ан+б«збаа;,~ = ~~~ ' — ам+бпа«1 — — О, См, например, Фвоввв«вссвв М.Л.„древа С Г.

Замечание о расправ«венин ошибок вгш решении снесены линейных уравнений прп помощи втврвпвоннорр врон«сев уу умн 1952. 7, вып.4. в1 Чтобы перна [[А ~ [[ была большая. Иначе в(А) булат мавб. Глава 10. Численные методы 188 учет которых при дифференцировании х = А 'Ь = (а';;)б дает дхг дан да'„ д' дага Окончательно, Прогнозы опять неутешительные. 10.4. Возмущения спектра Принципиальную роль в вопросах численного анализа играет влияние возмушений матрицы на ее спектр. Здесь возможны удивительные явления, способные пустить насмарку многие численные расчеты. Остановимся пока на вспомогательном результате. 10.4.1. Лемма.

Все собственные значения матрицы А лежат в обвединении кругов Гертгорина (г — агт( < Л; (з = 1,..., и), где В; =',у,(а,"(, либо Л; = ,'> (ау;1 )Ф УФ1 Если Л» — собственное значение А, то бег(А — Лад) = О, что влечет за собой (Ле -аа(< й; хотя бы для одного з. В противном случае (все (Ла -аь( ) й ) матрица А — ЛлХ имеет доминирующую диагональ, и потому — невырождена, ю> что исключает возможность бег (А — Ллд) = О. 10.4.2.

Теорема. Если матрица А диагонализируема, А=Т 'М', Л=д!а8(Лг,...,Лп), юГ См. угверждепие 9.4.! с последующим замечанием. 1ОА. Возмущения спектра 199 и Л' — собственное значение возмущенной матрицы А+ здА, то найдется такое Л;, что 1Л' — Л;( < ((Т(( ((Т '(( ((ЬА(( = о(А)((ЬА((, еде (( ° 11 обозначает одну из двух норм — строчную или столбцовую. Поскольку матрицы А+ ЬА и Т(А+ ьхА)Т ' = Л+ТгзАТ ' имеют одинаковые собственные значения, то проблема сводится к возмушению лнагональной матрицы Л. Пуси сч обозначают элементы матрицы Т1ЗАТ '. Лемма 1ОА,! гарантирует, что все собственные значения Л + ТгЛАТ ' лежат а кругах (х — Л; — сн( < з (сз(, пы которые, в свою очередь, содержатся в кругах (х — Л ( < ~ (с;,(, 3 что влечет за собой опенку (Л' — Л,(<((ТгЛАТ '(( < (Щ( ((Т '((„. ((ЬА(( .

Лналогично получается неравенство для нормы (( $. Таким образом, при возмущении ЬА возмущением спектра А замаскировано управляет матрица Т, приводящая А к диагональному виду. Задним числом это становится понятно. Но с самого начала догадаться не так легко, о чем свидетельствует история развития численных методов в докомпьютерную эпоху.

Многие разработанные тогда методы красиво выглядели на бумаге н1, но прн столкновении с вычислительной практикой на ЭВМ, сопрово:кдаемой неизбе:кными ошибками округления, — бьши полностью вытеснены из алгоритмического арсенала. В первую очередь это коснулось методов определения спектра матрицы, опиравшихся на вычисление характеристического полинома р„(Л) с последуюшим определением его корней. Обе задачи, вычисления коэффициентов и корней ра(Л), таят в себе много ловушек и характеризуются очень сильной зависимостью результатов счета от исходных данных и точности манипуляций.

В [19) приводится такой пример. Если у пслинома р(Л) = (Л вЂ” 1)(Л вЂ” 2) "(Л вЂ” 20), н) И почти ие проверялись фактически, поскольку решать вручную задачи хотя бы «! О на 1О никому не приходило в голову. Глава 1О. Численные методы имеющего корни (1,2,..., д1), изменить коэффициент прн а'з с — 210 всего лишь на -210+ 2 зз, то у возмущенного пояинома появдяегся, в частности, пара комплексно сопряженных корней с мнимыми частями жзз. Теперь достаточно выписать сопровождающую матрицу многочдена р(Л),— как получится пример матрицы 20 х 20, у которой изменение одного эяемента на величину 2 ~ (прябяизнтедьно на 2 м%) меняет спектр «ревояюционным образом.

Замечание. Формулировка теоремы 10.4.2 опирается на ограниченный список норм (строчную и столбцовую). Из эквивалентности всех норм в В" можно сделать вывод, что с той или иной долей натяжки (с добавлением некоторого множителя) норму в неравенстае (Л' — Л;(< ()Т(( ()Т '((-((гЛА(( можно считать любой. Соответствующий множитель будет не очень большим, если норма не очень вычурна, без больших перекосов'з). В естественных предположениях такой множитель вообще не требуется (равен единице). Наличие скрытого механизма, управляющего спектром матрицы при ее возмущении, показывает, что первоочередной интерес может представлять вовсе не фасад задачи. Возмущение спектра совсем редко фигурирует в прикладных постановках, но почти всегда присутствует в подводной части айсберга.