WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

имени М.В. ЛОМОНОСОВА

Факультет вычислительной математики и кибернетики

Н.М. Андрушевский

Анализ устойчивости решений

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

уравнений

Методическое пособие

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

Москва

_ 2008 УДК 378(075.8):512.64: 514.12 ББК 22.143: 22.151.573 А66 Печатается по решению Редакционно-издательского совета факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова Рецензенты:

Х.Д. Икрамов, д.ф.-м.н., профессор ВМиК МГУ;

М.В.Уфимцев, к.ф.-м.н., с.н.с. ВМиК МГУ Андрушевский Н.М.

А66 Анализ устойчивости решений систем линейных алгебраических уравнений: Учебное пособие. – М.: Издательский отдел факультета ВМиК МГУ имени М.В. Ломоносова (лицензия ИД N 05899 от 24.09.2001 г.); МАКС Пресс, 2008. – 71 с.

ISBN 978-5-89407-329- ISBN 978-5-317-02592- Учебное пособие посвящено исследованию устойчивости решений систем линейных алгебраических уравнений. На основе использования метода сингулярного разложения матриц предложены методика классификации матриц относительно меры их чувствительности к погрешностям в исходных данных и алгоритмы устойчивого решения плохо-обусловленных систем уравнений произвольного порядка и ранга. Предложенный математический аппарат может применяться в задачах определения по методу наименьших квадратов оптимальных параметров и их радиусов доверительной области для линейных математических моделей, а также численного решения интегральных уравнений типа свертки. Изложенные в пособии теоретические сведения и задачи практикума могут быть рекомендованы студентам старших курсов, специализирующимся в области математического моделирования.

© Факультет вычислительной математики ISBN 978-5-89407-329- и кибернетики МГУ имени М.В. Ломоносова, ISBN 978-5-317-02592- © Андрушевский Н.М., Учебное издание АНДРУШЕВСКИЙ Николай Матвеевич Анализ устойчивости решений систем линейных алгебраических уравнений Методическое пособие специального вычислительного практикума Издательский отдел Факультета вычислительной математики и кибернетики МГУ имени М.В. Ломоносова Лицензия ИД N 05899 о 24.09.01 г.

119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебные корпус Напечатано с готового оригинал-макета Формат 60х90 1/16. Усл.печ.л. 3,75. Тираж 100 экз. Заказ 659.

119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, Введение Задачи численного решения систем линейных алгебраических уравнений являются наиболее распространенными. Это связано с тем, что задачи определения оптимальных параметров математических моделей, статистической обработки данных, анализа изображений и сигналов, факторного анализа, экономики и другие при адекватном математическом описании сводятся к решению соответствующих систем линейных алгебраических уравнений.

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

В современных системах программирования научно-технических расчетов, таких как MATLAB, MATCAD, MATHEMATICA и других, имеются обширные библиотеки программ для решения разнообразных задач линейной алгебры. В библиотеках программ, подготовленных программистами-профессионалами, реализованы самые лучшие к настоящему времени алгоритмы, в основе которых лежат строгие математические обоснования. В целом этот программный продукт удовлетворяет самым высоким требованиям качества и освобождает пользователей от необходимости его усовершенствования. Однако это не освобождает пользователей от необходимости учитывать степень влияния погрешностей в исходных данных на результат получаемых решений даже в том случае, когда задачи линейной алгебры с неточными исходными данными решаются абсолютно точно. Суть в том, что влияние погрешностей в исходных данных имеет специфический анизотропный характер и, зачастую, даже незначительные погрешности случайного характера могут привести к тому, что полученные решения и истинные будут очень сильно отличаться. Благодушное забвение или игнорирование этих опасностей служит основой ложной интерпретации изучаемого явления или даже открытия научных псевдоэффектов.

В качестве иллюстрации рассмотрим простейший пример решения системы двух линейных уравнений:

Пусть в правой части находятся компоненты вектора y =. Тогда вектор x 0 = – точное решение рассматриваемой системы. Для результаты, получаем y 0 y 2 < y 0 y1, x 0 x 2 >> x 0 x1. Таким образом в рассматриваемом примере возмущение решения, вызванное меньшими погрешностями в правой части, значительно больше возмущения решения, вызванного большими погрешностями. Этот, на первый взгляд, парадоксальный факт обусловлен тем, что рассматриваемая невырожденная система относится к классу плохо-обусловленных систем. Именно для таких систем характерно появление больших возмущений в решениях при наличии малых возмущений в исходных данных. Поэтому при решении систем линейных алгебраических уравнений с погрешностями в исходных данных обязательно необходимо идентифицировать матрицы на предмет их хорошей или плохой обусловленности, определять количественную меру обусловленности и вычислять радиус доверительной области возмущенных решений в зависимости от меры чувствительности матриц к погрешностям и уровня погрешностей в исходных данных. Следует заметить, что используемое в данном пособии понятие плохой обусловленности системы отличается от того, которое используют специалисты по вычислительной линейной алгебре.

';

Суть этого различия в следующем. В практических приложениях часто приходится решать переопределенные системы линейных алгебраических уравнений A(x + x) = y + y с погрешностями y.

Для исследователей-практиков важное значение имеет коэффициент наибольшего возможного усиления абсолютной погрешности q=, когда заданы матрица A и уровень погрешности в правой части y. Естественно считать, что если q > 1, то система уравнений сильно чувствительна к погрешностям (плохо обусловлена), а если q 1, то система уравнений слабо чувствительна (хорошо обусловлена). Поскольку обобщенная (псевдообратная) матрица, 0 < min – наименьшее сингулярное число в сингулярном разложении матрицы A, y r – длина проекции вектора y на ранговое пространство матрицы A, то индикатором плохой обусловленности служит величина 0 < min < 1.

Именно в этом смысле используется термин “плохая обусловленность”. В то же время специалисты по вычислительной линейной алгебре используют понятие плохой обусловленности при вычислении коэффициента максимального усиления относительной погрешности c = cond ( A) =. Это число играет важную роль, в частности, для задачи обращения матриц. Однако, поскольку последнего неравенства невозможно точно определить максимально возможное расстояние между приближенным и истинным решениями, т.к. точные значения x и y априори неизвестны.

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

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

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

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

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

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

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

Автор выражает искреннюю благодарность коллегам – профессору Щедрину Б.М., профессору Икрамову Х.Д. и старшему научному сотруднику Уфимцеву М.В. – за доброжелательную критику и ценные замечания, способствующие улучшению изложения материала книги. Разумеется, это не снимает с автора ответственности за возможные упущения и недоработки.

Критические замечания по поводу содержания и формы изложения теоретического материала пособия просим присылать по адресу [email protected] Часть §1. Основная теорема линейной алгебры Любая прямоугольная матрица вещественных чисел, размера n k, может рассматриваться как математическая запись оператора, который осуществляет отображение абстрактного конечномерного вещественного пространства R k в другое конечномерное вещественное пространство R следующим образом:

Более кратко выражение (1) можно записать в матрично-векторном виде где x R k, y R n, a i R n, i = 1, 2,..., k – вектор-столбцы матрицы A. (Далее везде мы закрепляем символ x для векторов, принадлежащих “левому” пространству R k = X и символ y для векторов, принадлежащих “правому” пространству R n = Y ).

Представляя линейное преобразование (1) с помощью матрицы A мы предполагаем, что как в X так и в Y заданы ортогональные системы координат.

Из формулы (2) следует, что каждый вектор x однозначно отображается в некоторый вектор y, который представляет собой линейную комбинацию векторов a i R n, i = 1, 2,..., k, где весовыми множителями этой комбинации служат координаты вектора x.

Аналогично, транспонированная определяет оператор отображения в противоположном направлении конечномерного пространства R n R k, т.е.

где b j, j = 1, 2,..., n – вектор-столбцы матрицы AT (т.е. вектор-строки матрицы A ).

Длиной вектора z R l называется величина z = z1 + z 2 +... + zl2.

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

Величина (y, z ) = y T z = yi zi – скалярное произведение векторов.

Косинус угла между векторами y и z вычисляется по формуле cos = (y, z ) /( y z ). Векторы y и z ортогональны, когда (y, z ) = 0.

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

Определение 1. Если ни одна нетривиальная линейная комбинация векторов a1, a 2,..., a k R n не равна нуль-вектору то эти векторы называются линейно независимыми. В противном случае эти векторы называются линейно зависимыми, и один из них является линейной комбинацией остальных.

Между линейной независимостью и ортогональностью существует простая связь.

Теорема 1. Если ненулевые векторы x1, x 2,..., x k попарно ортогональны (каждый вектор ортогонален любому другому), то они линейно независимы.

Совокупность линейно независимых векторов y i, i = 1, 2,..., l, образует базис подпространства R l R n, размерность которого равна l.

Произвольный набор линейно независимых векторов может быть преобразован в набор попарно ортогональных векторов при помощи алгоритма Грама – Шмидта.

Максимальное число r линейно независимых вектор-столбцов матрицы A называется ее рангом. Векторы y = Ax, x R k, образуют множество значений матрицы A, и это множество называется ее образом в пространстве R n. Поскольку в матрице A имеются r k линейно независимых вектор-столбцов, то ее образом в пространстве R n будет подпространство, размерность которого также равна r. Это подпространство называют ранговым пространством (пространством столбцов) матрицы A и обозначают символом R (A), В матрично-векторном виде соотношение (4) можно записать в виде Ax = n, т.е. векторы a1, a 2,..., a k линейно зависимы тогда и только тогда, когда существует нетривиальное решение системы и, следовательно, удовлетворяющих системе уравнений (5), образует так называемое нуль-пространство N(A) матрицы A. Размерность нульdim N( A) = k r.

называется также ядром этой матрицы, а его размерность называется дефектом матрицы. Обозначим дефект матрицы символом (A).

Так как ранг транспонированной матрицы A T также равен r, то ее ранговое пространство R ( A T ), R ( A T ) R k, также имеет размерность r. Это подпространство называют еще пространством строк матрицы A. Соответственно, нуль-пространство N( A T ) имеет размерность n r.

Справедлива одна из наиболее важных теорем линейной алгебры:

Теорема 2.

Для произведения AB прямоугольных матриц A, размера k l, и B, размера l n, – справедлива следующая теорема.

Теорема 3. rank ( AB) rank ( A), rank ( AB) r (B), ( AB) (B).

В частности, если столбцы матрицы A линейно независимы, то для квадратной симметричной матрицы G = A T A имеем и матрица A T A является обратимой матрицей.

Перейдем к следующему важному понятию ортогональности двух подпространств.

Определение 2. Два подпространства U и V одного и того же пространства R n называются ортогональными, если каждый вектор u U ортогонален каждому вектору v V, т.е. скалярное произведение (u, v ) = 0 для всех u U и v V. (Факт ортогональности подпространств будем обозначать символом Пример 1. Пусть U является плоскостью, порожденной векторами u1 = (1, 0, 0, 0)T и u 2 = (1, 2, 0, 0)T, а V – прямая, порожденная вектором v1 = (0, 0, 3, 4)T. Тогда, так как вектор v1 ортогонален как к вектору u1, так и к вектору u 2, прямая V будет ортогональна к плоскости U, т.е. V U.

Прямой суммой W = U V подпространств U и V называется подпространство W = {w : w = u + v, u U, v V}.

Определение 3. Пусть подпространство U R n. Тогда подпространство всех n -мерных векторов, ортогональных к подпространству U, называется ортогональным дополнением к U и обозначается U, U U = R n.

Для любого подпространства U R n существует ортогональное дополнение U R n и если y R n, то найдутся единственные векторы u U и u U такие, что y = u + u. Для этих векторов выполняется теорема Пифагора:

пространство R ( A T ) и нуль-пространство N(A) являются ортогональными подпространствами в R k и выполняется условие т.е. R ( A T ) – ортогональное дополнение к N(A). Аналогично ранговое пространство R (A) и нуль-пространство N( AT ) являются ортогональными подпростанствами в R n :

R (A) – ортогональное дополнение к N( A T ).

Доказательство. Предположим, что u – произвольный вектор из нуль-пространства N(A). Тогда Au = n, т.е. вектор u ортогонален каждой вектор-строке матрицы A или, что то же самое, к каждому вектор-столбцу матрицы A T. Следовательно, он ортогонален ко всему пространству R ( A T ), порожденному этими столбцами. Это верно для любого вектора u из нуль-пространства N(A), и, следовательно, R ( AT ) N( A). Проводя аналогичные рассуждения для матрицы A T, получаем R ( A) N( A T ).

однозначно разложить в сумму однозначно разложить в сумму y = y r + y 0, где y r R (A), Таким образом, каждая матрица A вместе с транспонированной к ней матрицей A T выделяют, соответственно, в пространствах R k и R n две пары подпространств { R ( A T ), N( A)} и { R ( A), N( AT )}.

Теоремы 2 и 4 устанавливают чрезвычайно важные соотношения между этими основными подпространствами. Объединяя их вместе можно сформулировать теорему:

Основная теорема линейной алгебры. Для любой матрицы A размера n k справедливо:

Действие произвольной матрицы A показано (очень схематично) на рис. 1. Произвольный вектор x однозначно разлагается в сумму x = x r + x 0. Матрица A преобразует компоненту x r R ( A T ) в вектор Ax r = y r R (A), в то время как компонента x 0 N( A ) преобразуется в нулевой вектор n.

Рис. 1. Условное изображение расщепления пространств R k и R n.

Рис. 2. Условное изображение действия матрицы A T размера k n, Теорема 5. Отображение пространства строк пространство столбцов R (A) с помощью матрицы A невырожденное, т.е. обратимо: каждый вектор y из пространства столбцов является образом одного и только одного вектора x, принадлежащего пространству строк.

Доказательство. Если вектор y принадлежит пространству столбцов, то он является некоторой линейной комбинацией Ax столбцов матрицы A. Раскладывая вектор x в сумму x r + x 0, где Таким образом, мы нашли в пространстве строк подходящий вектор x r. Если бы там был другой вектор z r, такой, что Az r = y, то A(x r z r ) = y y = n. Поэтому вектор x r z r принадлежит как пространству строк R ( A T ), так и нуль-пространству N(A).

Следовательно, он ортогонален сам себе, а это возможно только для нулевого вектора, т.е. x r = z r.

Аналогично доказывается, что матрица A T является обратимым отображением в противоположном направлении из R (A) на R ( A T ).

Это не значит, что матрица A T является обратной к A, просто для каждого x R ( A T ) существует один и только один элемент y R (A) такой, что x = A T y. Действие матрицы A T показано схематично на рис. 2.

Каждая матрица A обратима, если ее соответствующим образом воспринимать как отображение некоторого r - мерного подпространства на другое r - мерное подпространство, а именно Основную теорему линейной алгебры можно сформулировать в виде альтернативы Фредгольма: для любых A и y одна и только одна из следующих задач:

имеет решение. Иначе говоря, либо вектор y R (A), либо существует такой вектор w N( A T ), что (w, y ) 0. Получить подходящий вектор w = y 0 можно, раскладывая вектор y в сумму Пример 2. Рассмотрим отображение R 3 R 2 с помощью матрицы Одномерное нуль-пространство N(A) порождается вектором x 0 = (2, 2, - 1)T и этот вектор ортогонален пространству строк R ( A T ), порождаемому векторами x r, 1 = (1, 0, 2)T и x r, 2 = (1, 1, 4)T. Ранговое y r, 2 = (0, 1)T, нуль-пространство N( A T ) состоит из единственного y 0 = (0, 0)T. Из основной теоремы линейной алгебры вектора заключаем что, например, вектор x = (1, 1, 1)T однозначно разлагается x 0 N( A ), а система уравнений имеет бесконечно много решений x = x r N(A) и общее решение имеет вид:

Основная теорема линейной алгебры дает четкие ответы на вопросы существования и единственности решений систем уравнений произвольного порядка Рассмотрим наиболее часто встречающиеся в практических приложениях системы с вертикально-прямоугольными матрицами Пусть вертикально-прямоугольная матрица A, размера n k, n k, имеет полный ранг r = k. В этом случае, dim N( A) = 0, взаимно однозначное отображение R k R (A) и обратное отображение R ( A) R k задается матрицей т.к. A 1 ( Ax) = ( A T A) 1 ( A T A)x = x. Матрица A 1 называется левой обратной к матрице A. Заметим, что матрица A 1 размера k n существует, т.к. по теореме 3 квадратная матрица G = A T A – обратима. В частности, если матрица A – полуортогональная (вектор-столбцы являются ортонормированными), то A 1 = A T.

При решении переопределенных систем уравнений Ax = y полного ранга возможны три ситуации:

имеет единственное нетривиальное решение Эквивалентные условия единственности решения:

1) вектор-столбцы матрицы A линейно независимы;

2) нуль-пространство N(A) содержит только нулевой вектор;

4) квадратная матрица A T A является обратимой.

Ненулевой вектор y N( AT ). Тогда система (8) является несовместной, т.к. для любого x k, вектор y = Ax N( A T ) ;

случае система (8) также является несовместной, т.к. для Для несовместных систем полного ранга Ax = y r + y 0 можно искать решение наилучшего приближения x opt такое, что для всех x R k выполняется неравенство Теорема 6. Значение функции (x) = Ax y достигает своего минимума в точке x pt, являющейся решением системы уравнений Тогда grad (x) = 2A T Ax 2A T y. Так как (x) > 0 для всех x, то из необходимого условия минимума квадратичной функции (x), а именно нормальных уравнений Система (13) имеет единственное решение x opt = ( A T A) 1 AT y и это решение называется оптимальным, потому что вектор является ближайшим к исходному вектору y = y r + y 0.

Поскольку для произвольного вектора y вектор является компонентой этого вектора в пространстве столбцов матрицы, то матрица суть матрица проектирования на пространство столбцов R (A).

Далее мы увидим, что в случае матриц неполного ранга матрица проектирования на пространство столбцов имеет аналогичный вид Pr = AA +, где A + – так называемая обобщенная (псевдообратная) матрица.

Вектор y Pr y является компонентой в ортогональном дополнении N( A T ). Поэтому матрица является матрицей проектирования на ортогональное дополнение к R ( A) (т.е. нуль-пространство N( A T ) ). Таким образом, имеем матричную формулу для разбиения вектора на две взаимно перпендикулярные составляющие:

Матрицы проектирования обладают специфическими свойствами:

Теорема 7. Матрица проектирования P = A( AT A) 1 AT обладает двумя основными свойствами – она является:

1) идемпотентной, т.е. PP = P ;

2) симметричной, т.е. P = PT.

И обратно, любая матрица с этими двумя свойствами представляет собой матрицу проектирования на свое пространство столбцов.

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

т.е. матрица идемпотентна. Для доказательства симметричности матрицы P рассмотрим два произвольных вектора y и z. Тогда векторы являются взаимно ортогональными:

Поскольку это справедливо для любых векторов y и z, получаем, что PT (E n P) = (0 nn ), т.е. PT = P T P, или P = PT P. Следовательно, PT = P. (Символ (0 nn ) обозначает нуль-матрицу размера n n ).

Для доказательства обратного необходимо, используя свойства 1) и 2), показать, что P является матрицей проектирования на свое пространство столбцов. Это пространство состоит из всех линейных комбинаций столбцов матрицы P. Для любого вектора y вектор Py обязательно лежит в этом пространстве. Кроме того, вектор y Py ортогонален этому пространству: для любого вектора Pz из пространства столбцов свойства 1) и 2) дают Поскольку вектор y Py ортогонален пространству столбцов, он и является искомым перпендикуляром, так что P оказывается матрицей проектирования. Матрица E n P также обладает этими двумя основными свойствами.

u1 = (1, 1, 0)T, u 2 = (1, 0, 1)T и вектор y = (0, 2, 1)T U. Тогда матрица A со столбцами u1 и u 2 имеет вид:

а матрица проектирования на подпространство R (A) :

Проекция вектора y на подпространство R (A) – y r = Pr y = (1, 1, 0)T ;

проекцией на ортогональное дополнение N( A T ) есть вектор y 0 = (E3 Pr )y = (1, 1, 1)T.

Для полуортогональных матриц A размера n k, k n имеем AT A = E k, и тогда матрицы проектирования на подпространства R (A) и N( AT ) вычисляются очень легко, что видно из следующего примера.

Пример 4.

Пусть для матрицы полного ранга мы решаем несовместную переопределенную систему уравнений Тогда оптимальное решение есть решение системы нормальных уравнений Так как оптимальное решение системы есть вектор и, следовательно, вектор y 0 не оказывает никакого влияния на величину оптимального решения, а только определяет длину вектора оптимальной невязки Следствие. В силу выше сказанного ясно, что при решении системы уравнений содержащей погрешности y = y r + y 0, y r R ( A), y 0 N( AT ), вектор y 0 не влияет на значение приближенного решения. Поэтому длина вектора оптимальной невязки y 0 не может служить характеристикой близости приближенного решения к истинному (см. рис. 3). Возмущение решения x = ( AT A) 1 AT y r зависит только от компоненты y r. Однако, длина x зависит не только от величины y r, но также от направления вектора y r, что будет подробно обсуждаться ниже. В частности, при фиксированном значении y, вектор x изменяется в диапазоне:

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

Рис. 3. Оптимальное решение не зависит от компоненты dy 0 N( AT ).

Рассмотрение вопросов решения систем уравнений с матрицами неполного ранга мы проведем после изложения метода сингулярного разложения матриц.

§2. Сингулярное разложение матриц Сингулярное разложение матриц (SVD – Singular Value Decomposition) является своеобразным “томографом высокого разрешения”. Этот метод позволяет определить ранг матрицы A, меру и тип обусловленности, найти ортогональные базисы подпространств R ( A), R ( A T ), N( A), N( AT ) и, самое главное, вычислить обобщенную обратную матрицу (псевдообратную), найти оптимальное решение несовместной системы уравнений с матрицами неполного ранга, приближенное решение систем уравнений с плохообусловленной матрицей полного ранга, радиус доверительной области приближенных решений и … многое другое! Великолепный набор качеств этого метода заслуживает его детального рассмотрения. Алгоритм SVD входит в десятку наиболее важных алгоритмических достижений 20-го века.

Напомним, что нижеследующие условия единственности решения системы уравнений Ax = y являются эквивалентными:

нуль-пространство N(A) содержит только нулевой квадратная симметричная матрица AT A является Для этого случая система Ax = y имеет единственное решение, которое вычисляется по сравнительно простой формуле:

Но если условия 1) 4) не выполняются и вектор x определяется из системы Ax = y неединственным образом или система несовместна, то необходимо определить псевдообратную матрицу A + такую, что x = A + y будет оптимальным решением по методу наименьших квадратов системы Ax = y.

Определение. Оптимальным среди всех решений системы Ax = y по методу наименьших квадратов является решение с минимальной длиной (евклидовой нормой).

Пусть рассматриваемая система уравнений с матрицей неполного ранга является совместной. Для отыскания оптимального решения вспомним, что пространство строк R ( AT ) и нуль-пространство N(A) представляют собой ортогональные дополнения друг к другу в пространстве R k. Это означает, что любой вектор может быть разложен на две перпендикулярные составляющие – проекцию на пространство строк и проекцию на нуль-пространство. Применим это разложение к одному из решений (обозначим его через x s ) системы возникают три существенных момента:

1) Компонента x r сама является решением системы Ax = y :

2) Все решения системы Ax = y имеют одну и ту же компоненту x r в пространстве строк R ( AT ) и отличаются лишь компонентой x 0 из нуль-пространства N(A), т.к. общее решение равняется сумме частного решения (в данном случае это x r ) и произвольного решения x 0 N(A) однородного 3) Длина такого решения x r + x 0 удовлетворяет теореме Пифагора, поскольку две компоненты взаимно ортогональны:

Отсюда мы заключаем: решением с минимальной длиной является вектор x r.

Оптимальным решением по методу наименьших квадратов произвольной системы Ax = y является вектор x r, удовлетворяющий двум условиям:

1) вектор Ax r равняется проекции вектора y на пространство 2) вектор x r принадлежит пространству строк R ( AT ).

Определение. Матрица A + называется псевдообратной к A, если для x r = A + y выполняются вышеприведенные условия 1) и 2).

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

проектировать вектор y на R (A), т.е. вычислять y r = Pr y ;

выбирать единственный вектор x из пространства строк R ( AT ), являющийся решением системы Ax = y r.

Один крайний случай возникает, когда вектор y перпендикулярен R (A), т.е. когда вектор y N( AT ). Тогда y r = n, x = k и матрица A + должна переводить все векторы из N( AT ) в нуль-вектор k.

Другая крайность состоит в том, что вектор y может лежать целиком в пространстве столбцов R (A) и тогда решение должно находится путем “обращения” матрицы A. (Мы уже отмечали в §1, что матрица A обратима, если рассматривать ее просто как отображение из ее пространства строк в пространство столбцов и обратной должна быть A + ). Из этого описания, подкрепленного иллюстрацией на рис. 4, можно сформулировать некоторые основные свойства псевдообратной матрицы:

1) Матрица A + имеет размер k n, т.к. она применяется к вектору 2) Пространство столбцов матрицы A + совпадает с пространством строк матрицы A, а пространство строк матрицы A + совпадает с пространством столбцов R (A). Заметим, что в качестве следствия получаем rank ( A + ) = rank ( A) ;

3) Псевдообратная к матрице A + есть матрица A ;

4) В общем случае AA + E n, поскольку матрица A может не иметь правой обратной, но матрица AA + всегда совпадает с матрицей Pr, осуществляющей проектирование на пространство столбцов R (A) :

Рис. 4. Проекционные действия псевдообратной матрицы A +.

Пример 5. Пусть Базисами пространства столбцов и пространства строк являются векторы e1 = (1, 0, 0)T и e 2 = (0, 1, 0)T, вектор e 3 = (0, 0, 1)T порождает нуль-пространства N(A) и N( AT ). Решение системы Ax = y начинается с проектирования y на пространство столбцов R (A) :

Затем решается система Ax = y r :

Решение выписывается легко: x1 = 0.1 y1, x2 = 2 y2 и x3 = t, t R.

Из этого бесконечного семейства решений выбираем одно, имеющее минимальную длину, полагая x3 = 0. Таким образом, мы получили решение x opt = (0.1 y1, 2 y2, 0)T, которое лежит в пространстве строк.

Это решение можно получить с помощью псевдообратной матрицы следующим образом. Если S = A, тогда Этот пример является типичным для всего семейства матриц S специального вида, имеющих в качестве первых r элементов главной диагонали положительные числа 1, 2,..., r и остальные элементы равны нулю. Псевдообратная S + к матрице S вычисляется легко:

первые r элементов на ее главной диагонали будут числа 1 / i, остальные равны нулю. Если матрица S имеет размер n k, то S + будет иметь размер k n. Легко убедится, что ранг матрицы S + равен рангу S, дефект матрицы S равен k r, дефект матрицы S + равен n r и (S + ) + = S, т.е. псевдообратная к S + совпадает с S.

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

Доказательство этой теоремы существенным образом опирается на известные теоремы линейной алгебры:

Теорема 8. Если A – симметричная матрица размера n n с действительными элементами, то её собственные значения – действительные числа.

Доказательство. Если ( A E)x = n, то и ( A *E)x = n, где * – комплексно сопряженная величина по отношению к. Следовательно, = *.

Теорема 9. Для матрицы A произвольного размера собственные значения симметричной матрицы G = AT A – неотрицательны, т.е.

Теорема 10. (О диагонализации матриц). Если A – симметричная матрица размера n n с действительными элементами и собственными числами 1, 2,..., n, то существует ортогональная матрица V такая, что где – диагональная матрица с диагональными элементами j собственных значений. Матрица V – ортогональная, столбцы матрицы V – собственные векторы матрицы A. При этом j -й столбец v j матрицы V соответствует j -му собственному вектору, т.е.

Теорема 11. (Сингулярное разложение матриц). Произвольная матрица A размера n k, n k может быть представлена в виде где U – ортогональная матрица размера n n, V – ортогональная матрица размера k k, а матрица S размера n k имеет специальную диагональную форму: на главной диагонали находятся числа i > 0, i = 1, 2,..., r, r k и i = 0, i = r + 1,..., k. Числа i называются сингулярными числами матрицы.

Доказательство. Доказательство справедливости утверждения (19) основано симметричной матрицы G = AT A, размера k k, существует ортонормированный набор собственных векторов v i, i = 1, 2,..., k, v i R k (которые образуют столбцы матрицы V ), Умножая скалярно на v i, получаем, что i 0 :

Предположим, что числа 1, 2,..., r положительны, а остальные k r векторов Av i и чисел i равны нулю. Для i > 0 положим единичными векторами, причем ортогональными (что вытекает из (20)):

Следовательно, мы имеем систему r ортонормированных векторов, которая может быть расширена до полного ортонормированного базиса u1, u 2,..., u r,..., u n, образующего столбцы матрицы U, при помощи алгоритма ортогонализации Грама-Шмидта. Тогда элементами матрицы UT AV будут числа uT Av j, равные нулю при j > r словами, матрица UT AV в точности совпадает со специальной матрицей S, у которой на главной диагонали расположены числа i > 0, i = 1, 2,..., r и i = 0 для i = r + 1,..., n. Следовательно, Псевдообратная матрица вычисляется по формуле:

Эта формула доказывается непосредственно из принципа наименьших квадратов. Минимизируемая невязка Ax y с учетом разложения (19) имеет вид:

Так как умножение на ортогональную матрицу UT не изменяет длину вектора Ax y, то Введем новый неизвестный вектор x / = V T x = V 1x, длина которого совпадает с длиной вектора x. Тогда будем минимизировать величину Sx / U T y, и оптимальное решение x / opt (т.е. решение с минимальной длиной) имеет вид x / opt = S + UT y. Следовательно, оптимальное решение системы Ax = y есть Следовательно, Pr = AA + является матрицей проектирования на подпространство R (A).

Матрица A + называется обратной матрицей Мура – Пенроуза, поскольку именно они ввели это понятие, или обобщенной обратной к A. Следует отметить, что название “обобщенная обратная” применяется к другим матрицам, которые обладают не всеми свойствами матрицы A +. Именно поэтому чаще пользуются термином “псевдообратная”.

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

Из определения нормы непосредственно следует, что:

1) cA = c A для всех вещественных c и всех A ;

2) ( ) = 0 и A > 0, если A ( ) (здесь ( ) означает нулевую Из определения нормы (25) также вытекает, что для всех x и A, причем равенство достигается, по крайней мере, на одном ненулевом векторе.

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

где max ( AT A ) есть наибольшее собственное значение матрицы G = AT A. Таким образом Поскольку квадраты сингулярных чисел i матрицы A являются (по построению) собственными числами матрицы AT A, то другой не изменяют длины векторов и наибольший увеличивающий множитель равен наибольшему сингулярному числу max.

Вектор v, v = 1, который при отображении матрицей A увеличивается максимальным образом, является собственным вектором матрицы AT A, соответствующим наибольшему собственному значению:

Норма Фробениуса (называется еще евклидовой матричной нормой – аналог евклидовой нормы векторов) матрицы A определяетcя формулой соотношениям где A – матрица размера n k, m = min(n, k ).

Для произведения матриц справедливо неравенство:

и максимизируя, приходим к неравенству (29).

Неравенство треугольника для матричных норм: из неравенства треугольника для векторов имеем Ax + Bx Ax + Bx. Разделив это неравенство на x и максимизируя, получаем Обе названные нормы удовлетворяют мультипликативным неравенствам:

Спектральная норма псевдообратной матрицы A + есть число Числом обусловленности (condition number) матрицы A называется величина Это число фигурирует в неравенстве для оценки относительной погрешности решения системы A(x + x) = y + y, а именно Действительно, так как Ax = y, Ax = y, то непосредственно из (26) получаем, что Из неравенства (33) следует, что для матриц с большим числом обусловленности относительная погрешность решения системы уравнений A(x + x) = (y + y ) может значительно превышать относительную погрешность в правой части. Однако практическая ценность этого неравенства мала, поскольку неизвестными содержательные результаты можно получить при вычислении оценок абсолютной погрешности решения. Именно оценки абсолютных погрешностей решений более всего интересуют специалистовприкладников. Эти вопросы подробно рассматриваются в следующем параграфе.

Сформулируем общий итог теоремы о сингулярном разложении матриц:

2. Количество отличных от нуля сингулярных чисел определяет 4. Алгоритмы сингулярного разложения построены таким образом, что сингулярные числа вычисляются в невозрастающем порядке. Поэтому первые r столбцов матрицы U подпространства N( AT ) ;

5. Первые r столбцов матрицы V образуют ортогональный базис подпространства R ( AT ), остальные k r столбцов образуют ортогональный базис подпространства N(A) ;

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

7. Определитель невырожденной матрицы удовлетворяет условию det( A ) = det(U ) det(S) det(V T ) = 1 2... n, так как определители ортогональных матриц U и V равны ± 1.

§3. Спектральная классификация матриц произвольного размера и критерии плохой обусловленности Характерной особенностью операций отображения конечномерных пространств с помощью матрицы A является простота вычислений результатов отображений и возможность геометрической интерпретации этих результатов (для больших размерностей – на интуитивном уровне по аналогии с двух- и трехмерными пространствами).

смысле, что В частности, прямолинейный отрезок отображается в прямолинейный отрезок Деформация различных множеств или даже всего пространства при отображениях зависит от корпоративной структуры совокупности вектор-столбцов a i, i = 1, 2,..., k. Выяснение особенностей картины деформаций при отображениях будет предметом нашего особого внимания.

Пример 6. Рассмотрим упоминавшуюся во введении матрицу Эта невырожденная матрица задает отображение R 2 R 2 :

Так как A t e1 = a1, A t e 2 = a 2, где e1, e 2 – орты стандартного базиса, то на основании (36) получаем, что прямолинейный отрезок отображается в отрезок Соответственно, множество точек на сторонах квадрата Qx = { x : x1 + x2 = 1 } отображается на стороны параллелограмма, вершины которого задаются векторами { a1, a 2, a1, a 2 }. Таким образом, мы установили, что матрица A t при отображении деформирует квадрат Qx в параллелограмм и осуществляет его поворот. Очевидно, что степень деформации и угол поворота зависят от корпоративной структуры вектор-столбцов матриц, а именно: чем меньше углы между вектор-столбцами и чем больше различие в их длинах, тем больше эффект деформации. Эффект деформации отсутствует, когда A – тождественное отображение.

Топология эффекта деформации более содержательна, если рассмотреть отображение окружности x = {x : x = 1}. Матрица A t отображает окружность x в сильно вытянутый эллипс, длины полуосей li которого равны значениям сингулярных чисел матрицы A t, а именно: l1 = 1 = 7.34, l2 = 2 = 0.27. Соответственно, матрица A t+ = A t 1 отображает единичную окружность y в эллипс, длины осей которого l1 = 1 / 1 0.14 и l 2 = 1 / 2 3.7 (см. рис. 5б, стр. 37).

Большое значение cond ( A t ) = 1 / 2 = 26.96 сигнализирует о большой деформации окружности при ее отображении матрицей A t и возможной плохой обусловленности системы уравнений A t (x + x) = y + y. Действительно, так как 2 < 1 и x = A t+y, то x A t+ y = (1 / 2 ) y и, следовательно, длина погрешности решения может увеличиваться в 1 / 2 раз по сравнению с длиной вектора погрешности y при наиболее неблагоприятной его ориентации. На рис. 5а и 5б приводится геометрическое объяснение “парадоксального” результата, когда погрешность y 2 < y приводит к погрешности x 2 >> x1. Это обусловлено тем, что матрица A t1 отображает единичную окружность в сплюснутовытянутый эллипс большой анизотропии ( cond ( At ) = 26.96 ).

Рассматриваемая система уравнений действительно является плохообусловленной. В зависимости от ориентации вектора y (фиксированной длины), длина вектора x = At1y может достигать максиA t+ y = (1 / min ) y >> y. В нашем мальной величины x max случае вектор y + y 2 отображается с помощью матрицы A 1 в точку значительно дальше, чем точка x + x1 = A t1 (y + y1 ). Такой поразительный эффект вызван именно тем, что направление y1 – наиболее благоприятное и совпадает с направлением первого собственного вектора (1 53.88) матрицы AT A t, а направление y 2 – наиболее неблагоприятное и совпадает с направлением второго собственного вектора ( 2 0.073 ).

Следует заметить, что большое значение числа обусловленности матрицы не является признаком плохой обусловленности системы относительно абсолютной погрешности. Например, для матрицы D = diag (1000,10), cond (D) = 100, однако x D 1 y = 0.1 y, т.е. система уравнений хорошо обусловлена.

Определение.

A(x + x) = y + y хорошо обусловлена, если x y r и плохо обусловлена, если x > y r, где y r – проекция вектора y на ранговое пространство R (A).

Так как x A + y = (1 / min ) y r, то можно сформулировать эквивалентные критерии обусловленности:

min 1 – система уравнений хорошо обусловлена;

0 < min < 1 – система уравнений плохо обусловлена.

Далее мы покажем, что эти критерии справедливы для матриц произвольного размера и ранга.

Рис. 5а. Погрешности y1 и y 2 коллинеарны собственным Рис. 5б. Сильная анизотропия при отображении обратной матрицей приводит к существенному различию возмущенных решений.

Сингулярное разложение матриц позволяет получить геометрическую картину топологии отображений R R.

Теорема 12. Матрица A, произвольного размера n k и ранга r, отображает гиперсферу x = x : x = 1, x R k в гиперэллипсоид E y R (A), размерность которого равна r. Аналогично, матрица A + отображает гиперсферу y = y : y = 1, y R n в гиперэллипсоид E x R ( AT ) размерность которого также равна r.

Доказательство. Рассмотрим ортогональное преобразование V системы координат в пространстве R k = X, в результате которого вектор x получит новое преставление x /, где x = Vx /. Таким же образом, применяя другое ортогональное преобразование U координат в R n = Y, мы получим новые координаты y, именно y /, где y = Uy /. Если U и V – матрицы из сингулярного разложения матрицы A, тогда В новой ортогональной системе координат преобразование с помощью матрицы A имеет очень простое представление:

Преобразование y / = S x / просто отображает первую координатную ось пространства X / в первую координатную ось пространства Y / с коэффициентом растяжения 1 > 0. То же самое проделывается со 2-й, 3-й,…, r -ой координатными осями пространства X /, причем 2, 3,..., r играют роль соответствующих коэффициентов растяжения. Последующие (r + 1) -я, …, k -я координатные оси X / отображаются в нулевой вектор n пространства Y /.

Из соотношений (37) следует, что матрица S отображает единичную гиперсферу гиперэллипсоид E y, E y R (A) векторов y / таких, что т.е. длины полуосей определяются значениями сингулярных чисел i > 0. Следует отметить, что в (38) стоит именно знак нестрого равенства, так как проекцией гиперсферы на подпространство меньшей размерности является гипершар.

Как уже отмечалось ранее, численные алгоритмы сингулярного невозрастающем порядке (т.е. 1 2... r > 0 ). Поэтому в E y наиболее удаленная точка имеет координаты y / max = ( 1, 0,..., 0)T, а y / min = (0,..., r, 0,..., 0)T. Аналогично, матрица S + отображает гиперэллипсоид E x R ( AT ), длины полуосей которого равны 1 / i, i > 0.

Свойство линейности операции отображения с помощью матрицы A своеобразно проявляется в следующем. Семейство концентрических гиперсфер в R k с центром x c отображается в виде концентрических гиперэллипсоидов в R n с центром y c = Ax c.

Поэтому действие матрицы A можно интерпретировать как действие x c k N(A), то “линза” A концентрирует гиперэллипсоиды в R n вокруг начала координат. Соответствующим своеобразным свойством обладает и псевдообратная матрица A +, которая отображает концентрические гиперсферы с центром y c из R n в гиперэллипсоиды в R ( AT ) с центром x c = A + y c. В обоих случаях размерности этих гиперэллипсоидов определяются количеством ненулевых сингулярных чисел.

Важную информацию можно извлечь из анализа спектра сингулярных чисел. Всевозможные матрицы целесообразно разбить на 4 типа относительно распределения сингулярных чисел:

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

Матрицы первого типа отображают гиперсферу x = {x : x = 1} в гиперэллипсоид, у которого длины каждой из полуосей больше единицы. Эти матрицы представляют оператор растяжения, и, соответственно, A + – оператор сжатия. Длина вектора погрешности решения для систем уравнений с такими матрицами удовлетворяет неравенству и, следовательно, системы уравнений с матрицами такого типа являются хорошо-обусловленными.

Очевидно, что ко второму типу относятся все ортогональные и полуортогональные матрицы, которые при отображении не изменяют длину векторов, так как Ax = (xT AT Ax) = x. Для таких матриц A = A + = 1, поэтому справедливо равенство т.е. системы уравнений с матрицами такого типа – нейтральнообусловлены.

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

И, наконец, матрицы четвертого типа осуществляют сжатие (вообще говоря, с различными коэффициентами сжатия 0 < i < 1).

Соответственно A + осуществляет растяжение. Для таких матриц справедливо неравенство т.е. для всевозможных ориентаций вектора y имеем x > y r, а это означает – матрицы четвертого типа заведомо плохообусловлены.

Общий вывод: системы уравнений с матрицами первого и второго типов – хорошо-обусловлены, а с матрицами третьего и четвертого типов – плохо-обусловлены.

На рис. 6а 6г показаны действия (2 2) -матриц и обратных к ним всех типов, где отчетливо видна взаимно ортогональная ориентация эллипсов прямого и обратного отображений окружности.

Рис. 6а. Отображение окружности матрицей первого типа:

Рис. 6б. Отображение окружности ортогональной матрицей:

Рис. 6в. Отображение окружности матрицей третьего типа:

Рис. 6г. Отображение окружности матрицей четвертого типа:

При решении систем линейных уравнений A(x + x) = y + y, содержащих погрешности в правой части, длина вектора погрешности решения удовлетворяет неравенству при этом из (37) следует, что равенство достигается тогда, когда в новой ортогональной системе координат y / = (0,..., 0, y r, 0,..., 0)T.

Из неравенства (40) и предложенной классификации матриц (39) следует, что:

а) для матриц первого и второго типов длина вектора погрешности решения никогда не превышает длины компоненты y r вектора погрешности правой части;

б) для матриц третьего типа длина вектора погрешности решения может превышать или не превышать y r (в зависимости от ориентации y );

в) для матриц четвертого типа длина вектора погрешности решения всегда превышает y r.

Таким образом, матрицы третьего и четвертого типов естественно называть плохо-обусловленными. Число q = 1 / min – коэффициент максимального усиления длины вектора погрешности решения, а конечномерного отображения с помощью матрицы A.

Вектор y в системе уравнений A(x + x) = y + y является зачастую результатом погрешностей экспериментальных измерений и по своей природе является случайной величиной. Направление y непредсказуемо и, в общем случае, y = y r + y 0, y r R (A), y 0 N( AT ). Так как A +y 0 n, то радиусом доверительной области (максимальное уклонение возмущенного решения x + x от истинного) является величина В принципе, величину y можно оценить достаточно точно из условий проведения эксперимента, а y 0 = Ax opt (y + y ) есть значение оптимальной невязки в задаче МНК. Так как y r y 0, то оценить более точно:

Специального рассмотрения заслуживает случай, когда в спектре распределения сингулярных чисел наблюдаются быстрый спад или пороговый нырок к нулю. В этом случае матрица A является близкой к вырожденной и заведомо плохо-обусловленной. Наличие вычислительных погрешностей в значениях малых сингулярных чисел может привести к огромным погрешностям при вычислении псевдообратной матрицы A + и, соответственно, оптимальное решение x opt = A + y будет содержать большие искажения. Разумным подходом является вычисление приближенного оптимального решения, применяя способ замены малых сингулярных чисел на некоторое пороговое значение l. Замена истинной матрицы A в системе уравнений Ax = USV T x = y на приближенную A = USV T, приближенное решение x opt,app = A + y будет отличаться от x opt = A + y. Относительную погрешность решения x / x можно оценить, используя матрицы Тогда §4. Линейные математические модели: оптимальные параметры и радиус доверительной области При обработке и интерпретации экспериментальных данных возникает задача установления функциональной зависимости между группами переменных t = (t1, t 2,..., t n )T и f = ( f1, f 2,..., f n )T. Мы будем считать независимыми переменными компоненты вектора t, влияющими на значения компонент вектора f по некоторому закону f = F (t, p, q). Функциональная зависимость F (t, p, q), принадлежащая некоторому параметрическому семейству функций математической моделью взаимосвязи между наблюдаемыми величинами.

В самой общей постановке, задача установления функциональной взаимосвязи включает в себе две задачи:

1. Выбор математической модели, которая адекватно описывает изучаемое явление;

2. Отыскание оптимальных параметров p opt и q opt, при которых соответствует опытным данным.

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

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

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

На практике радиоактивность измеряется в дискретные моменты времени и показания счетчика не будут точно соответствовать формуле (44), так как всегда присутствуют экспериментальные погрешности измерений. Вместо этого мы имеем серию показаний f1, f 2,..., f n в различные моменты времени t1, t 2,..., t n и соотношение (44) выполняются лишь приближенно:

В общем случае система уравнений (45) является несовместной и тогда, используя метод наименьших квадратов, возникает задача поиска оптимальных значений параметров p1, p2, q1, q2, при которых достигается минимальное расхождение между теоретическими и наблюдаемыми значениями f, т.е. решается задача Параметры q1 и q2 в математической модели (44) входят нелинейным образом. Задача поиска глобального минимума нелинейного функционала (46) связана с определенными вычислительными трудностями и для ее решения требуется применение специальных вычислительных методов.

Мы остановимся на рассмотрении отдельного класса задач МНК, когда математические модели выбираются в виде линейной комбинации некоторого количества базисных функций, а именно где p j – компоненты вектора искомых параметров.

Математические модели вида (47) называются линейными математическими моделями. Для таких моделей уравнения (45) записываются в виде системы линейных алгебраических уравнений Fp = f :

Матрица F, размера n k, n > k, имеет вид и называется матрицей плана. Такое название связано с тем, что численные значения элементов матрицы F определяются запланированным выбором базисных функций и точек измерений ti наблюдаемой зависимости f (ti ) = f i.

В общем случае, когда наблюдаемые значения f i содержат погрешности, переопределенная система уравнений (48) является несовместной. Это означает, что вектор f не принадлежит ранговому оптимальное решение в смысле наименьших квадратов системы Fp = f вычисляется по формуле где F + – псевдообратная матрица Мура – Пенроуза, а радиус доверительной области искомых параметров оценивается по формуле где: f – длина вектора погрешности, оцениваемая из условий в задаче МНК.

Рассмотрим несколько популярных математических моделей.

1. Математическая модель вида f (t ) = p1 + p2t является простейшей полиномиальной моделью. Поскольку базисными функциями является набор {1 (t ) = 1, 2 (t ) = t}, то для такой модели матрица плана имеет вид:

Квадраты сингулярных чисел матрицы F есть собственные значения матрицы нормальных уравнений Докажем, что для рассматриваемой математической модели можно применить специальное преобразование, при котором матрица F будет хорошо обусловленной. Для этого рассмотрим математическую ческий центр точек то рассматриваемая математическая модель генерирует матрицу Fc такую, что матрица соответствующей системы нормальных уравнений принимает диагональный вид Масштабирующий множитель w необходимо выбрать так, чтобы выполнялось неравенство матрицы и, следовательно, сингулярные числа матрицы Fc будут больше единицы, т.е. матрица Fc принадлежит к классу хорошообусловленных матриц. Легко убедиться, что между параметрами p1, p2 и q1, q2 существует простая взаимосвязь:

2) Математическая модель f (t ) = p1 exp( p2t ) редуцируется к простейшей линейной модели g (t ) = ln f (t ) = q1 + q2t, где q1 = ln p1, 3) Математическая модель f (t ) = p1 exp( p2 (tc t ) 2 ) редуцируется = tc t + s, q1 = ln p1, q2 = p2. Матрица плана такой модели имеет вид:

соответствующая ей матрица нормальных уравнений Для заданной серии точек { ti } можно выбрать такое s, чтобы добиться хорошей обусловленности матрицы F. Другими словами, необходимо выбирать такое значение s, чтобы для собственных значений матрицы G выполнялось условие min > 1.

4) Математическая модель в виде полинома степени k генерирует матрицу плана:

Спектр сингулярных чисел матрицы F существенным образом зависит от распределения точек { ti }, поэтому матрица F может с большой вероятностью принадлежать к классу плохообусловленных матриц. Это связано с тем, что для базисных функций t i, i = 0, 1,..., k, k 3 не существует конечного интервала, на котором эти функции были бы попарно ортогональными. Именно поэтому аппроксимация функций с помощью алгебраического полинома высокого порядка не применяется в практических приложениях.

Примером задачи с плохой обусловленностью является следующая задача.

5) Полиномиальная аппроксимация функций по значениям алгебрраических моментов.

Пусть на отрезке [0, 1] задана функция f (t ) и известно множество моментов (Значения mi, полученные путем численного интегрирования, возможно, содержат некоторые погрешности). Ставится задача аппроксимации функции f (t ) алгебраическим полиномом P(t ) степени k :

Умножая (51) последовательно на t j, j = 0, 1, 2,..., k, и интегрируя на [0, 1], получаем систему уравнений Gp = m с матрицей Гильберта (элементы матрицы вычисляются по формуле g ij = 1 /(i + j 1) ):

Поскольку углы между вектор-столбцами матрицы G малы, то следует ожидать, что матрица плохо-обусловлена. На самом деле, матрица Гильберта относится к числу плохо-обусловленных матриц третьего типа. Характерная особенность этой матрицы в том, что при возрастании ее порядка минимальные собственные числа (сингулярные числа) очень быстро стремятся к нулю. Матрица Гильберта является плохо-обусловленной и уже для k > 10 ничтожно малые погрешности в правой части системы G (p + p) = m + m могут вызвать гигантское увеличение p. Глубинная причина этого эффекта в том же: для базисных функций существует интервала, на котором даже первые три функции были бы ортогональны. Именно поэтому в практических приложениях не используется аппроксимация функций алгебраическим многочленом порядка k > 3. Существенно предпочтительнее использовать ортогональные многочлены (например, многочлены Лежандра, Чебышева и др.).

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

6) Аппроксимация функций тригонометрическим многочленом.

Пусть на отрезке [0, 1] задана функция f (t ) и известно множество коэффициентов Фурье Численные значения cl возможно содержат некоторые погрешности.

Ставится задача аппроксимации функции f (t ) тригонометрическим многочленом Tk (t ) степени k :

Функции {exp(i 2lt ), l = 0, 1, 2,..., k} – ортогональны на интервале [0, 1], т.е. 0 exp(i 2 ( j l )tdt = jl. Умножая (52) последовательно на exp(i 2lt ), l = 0, 1, 2,..., k, и интегрируя на [0, 1], получаем систему уравнений где: E – единичная матрица, c* – вектор комплексно сопряженных коэффициентов Фурье. Из (53) следует, что p c* и p c*, т.е. задача аппроксимации функции тригонометрическим многочленом является нейтрально-обусловленной.

В общем случае, доверительный радиус оптимальных параметров выбранной (возможно адекватной) линейной математической модели зависит от обусловленности соответствующей матрицы плана F и, конечно, от точности экспериментальных данных. Отметим, что по визуальному анализу графического изображения дискретного набора { ti, f (ti )} невозможно судить о качестве эксперимента.

Действительно, если вектор погрешностей f = f r + f 0, где f r принадлежит ранговому пространству R (F), а f 0 лежит в нульпространстве N(F T ) и тогда F +f 0 k, то для двух серий измерений { ti, f1 (ti )} и { ti, f 2 (ti )} таких, что 1,r f = 2,r f, а 1,0f 2,0f имеем f + 1f f + 2f, однако оценки оптимальных параметров в обоих случаях тождественно совпадают. Такие серии экспериментальных измерений являются эквивалентными в смысле оценки оптимальных параметров по МНК. Приведенные рассуждения можно подтвердить f (t ) = 7 4t + t 2. Две серии погрешностей “экспериментальных” данных моделировались с помощью датчика случайных чисел, распределенных по нормальному закону с различными дисперсиями.

Затем, после разложения векторов погрешностей на ортогональные составляющие, образованы новые векторы погрешностей 1f и 2f такие, что 1,r f = 2,r f, а 1,0f 2,0f. Численные значения “экспериментальных” данных изображены графически на рис. и приведены в таб. 1. Обе серии “экспериментальных” значений дают одинаковые оптимальные параметры хотя визуальный анализ графического изображения дает предпочтение первой серии измерений (на рис. 7 эти данные изображены (–*–) линией). В принципе возможна ситуация, когда но 1,r f a Легко убедиться, что представляет собой скользящее среднее значение функции f (t ).

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

Многократная свертка прямоугольного импульса является гладкой функцией с непрерывными производными до (n 1) го порядка. Так, например, 3,a (t ) состоит из трех гладко сшитых параболических отрезков:

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

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

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

Пусть { f1, f 2,..., f m } и {h1, h2,..., hn } – дискретные выборки с постоянным шагом значений функций f (t ) и h(t ). Объем этих выборок может быть различным. Образуем векторы размерности k = m + n следующим образом:

Необходимость дополнения нулевыми компонентами вызвана тем, что при свертке результирующий объем выборки k = m + n.

Вектор g = h f называется сверткой векторов, если его компоненты вычисляются по формуле Выражения (56) можно записать в матрично-векторном виде где квадратная ленточная матрица H + 0, размера (m + n) (m + n) и шириной ленты n, имеет вид:

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

Из ленточной структуры матрицы H + 0 видно, что дополнение вектора f нулевыми компонентами не изменяет значений компонент вектора свертки g и, кроме того, g m+n 0. Поэтому уравнение (57) можно заменить эквивалентным уравнением где ленточная матрица H1, размера (m + n 1) m и шириной ленты n, имеет вид:

Алгоритм построения матрицы H1 простой: ее вектор-столбцы суть где T j – оператор циклического сдвига компонент вектора h + 0 вниз на ( j 1) позиций.

Если h1 0, то матрица H1 имеет полный ранг r = m. Однако ленточные матрицы такой структуры принадлежат к третьему типу обусловленности, поэтому оптимальное решение предпочтительнее вычислять по формуле f opt = H1 g нежели по формуле f opt = H 1g.

При больших объемах выборок m и n необходимо проводить анализ спектра сингулярных чисел и вычислять приближенное оптимальное решение f opt,app, применяя процедуры пороговой модификации сингулярных чисел.

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

Задания специального вычислительного практикума предназначены для более глубокого усвоения теоретического материала, изложенного в предыдущих параграфах. Компьютерные вычисления рекомендуется выполнять в среде системы программирования научно-технических расчетов MATLAB. Отчеты о выполненных заданиях должны содержать постановки задач, комментарии к полученным результатам и их графические изображения. Следуя рекомендациям Декарта, необходимо проявлять инициативу самостоятельного любопытства и творческого поиска.

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

1. Легко ли открыть “псевдоэффект” ?

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

b0 = – точные значения коэффициентов в правой Пусть части. Тогда x0 = – точное решение системы.

Если коэффициенты содержат погрешности измерений, например Пусть при более тщательном измерении коэффициентов имеем r 7. Этот результат может служить основой интерпретации Очевидно, что b0 b2 > x0 x1 !!!

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

Для каких матриц будут иметь место аналогичные эффекты ?

Указать класс матриц таких, что если 2. Какие решения получают, решая несовместные системы уравнений ?

Почему для всякой несовместной СЛАУ Ax = b система уравнений A Ay = A b всегда совместна и имеет, возможно, бесконечно много решений ?

Пример: Система уравнений бесконечно много решений: y = 21 / 50 + 3. “Полезные ископаемые” на различных сериях экспериментальных данных.

Для описания функциональной зависимости выбрана некоторая линейная математическая модель f ( p, t ) = pi i (t ). Оптимальные параметры pi для выбранной модели определяются путем решения задачи МНК. Предположим, что имеются две серии экспериментальных значений f j, j = 1, 2,..., n, n > n p, измеренных в одних и тех же точках t j, однако с существенно различными уровнями погрешностей измерений.

Могут ли совпадать значения оптимальных параметров, вычисленные по этим сериям измерений ?

Могут ли две серии измерений с одинаковым уровнем погрешностей, дать существенно различные оценки оптимальных параметров ?

4. Волшебное превращение Золушки в прекрасную Принцессу.

Пусть квадратная матрица A такая, что вектор-столбцы этой матрицы являются попарно ортогональными, т.е. A A = D, D – диагональная матрица. Однако вектор-строки этой матрицы могут и не быть попарно ортогональными, то есть матрица AA не является диагональной. Почему матрица H = AD, где D – диагональная матрица с диагональными элементами d ii = 1 / d ii является унитарной, то есть Этот факт – своеобразный “бриллиант” линейной алгебры !

Каковы его полезные применения?

Тема 1.Топология отображений конечномерных пространств матрицами различных типов обусловленности 1. Сформировать матрицы A i, i = 1, 2, 3, 4, размера 2 2, различающиеся типом обусловленности. Какого типа будет матрица С помощью этих матриц выполнить отображение R 2 = X R 2 = Y следующих множеств точек M (x) :

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

д) M Chebur (x) – контуры графического изображения Чебурашки.

Будут ли на множествах M Chebur,i (y = A i x) присутствовать изображения веселых улыбок или гримасы разочарования?

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

ТОМ МОТ

ж) M VIP (x) – задается в соответствии с эстетическими вкусами и уровнем фантазии исполнителя.

Указания:

а) Матрицы A i должны быть общего вида (т.е. не диагональные);

б) Значения параметра a выбираются так, чтобы отчетливые графические изображения каждой пары множеств M j (x) и M j (y ) умещались на одной странице формата А4;

в) Формирование матриц различного типа обусловленности проще всего выполнить следующим образом. Очевидно, что матрица является ортогональной, т.е. это матрица второго типа. Далее определим матрицу Тогда, задавая значения t1 > 1 и t 2 > 1, t1 t 2, получаем матрицу первого типа. Задавая t1 > 1 и 0 < t 2 < 1 имеем матрицу третьего типа, а для 0 < t1 < 1 и 0 < t 2 < 1, t1 t 2 получаем матрицу четвертого типа.

г) Формирование множества M VIP (x) является обязательным для каждого исполнителя!

2. Сформировать матрицу третьего типа A 3 размера 2 2, число обусловленности которой cond ( A 3 ) 100. Задать вектор x и вычислить y1 = A 3 x1. Задать вектор погрешности y. Определить при каких ориентациях y 0.03 y1 ) длины векторов x + x = A 31 (y1 + y ) будут достигать своего наименьшего и наибольшего значений?

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

3. С помощью некоторой матрицы A, размера 5 2 и ранга 2, выполнить отображение R 2 R 4 множества точек x = {x : x = 1}.

Чтобы выяснить, что представляет собой множество y = {y : y = Ax, x = 1} можно воспользоваться одним из следующих способов:

а) Построить специальный летательный аппарат, произвести полет над ранговым пространством R (A) и визуально изучить множество y ;

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

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

Сравнить его площадь с площадью единичного круга;

в) Произвести нормировку векторов из множества y и сформировать e = {e = Ax / Ax }. Изобразить графически множество векторов x = A 1e, e e и объяснить полученный результат.

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

Тема 2. Сингулярное разложение матриц и его различные применения 1. Найти размерности и ортогональные базисы четырех основных подпространств R (A), N( A), R ( A T ) и N( AT ) матрицы A :

Определить тип матрицы и число обусловленности. Разложить вектор y1 = (1, 2, 3, 4, 5, 6)T на ортогональные составляющие y1 = y r + y 0, y r R (A), y 0 N( AT ). Используя сингулярное разложение матрицы найти оптимальное решение и оптимальную невязку для системы Ax = y1. Найти вектор y 2 такой, что x opt = A + y1 = A + y 2. Найти наиболее и наименее благоприятные ориентации вектора погрешности фиксированной длины.

2. Для ленточной матрицы A m,n размера (m + n 1) n, m = 5, n = 4, вычислить спектр сингулярных чисел, определить тип и число обусловленности.

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

3. Элементами матрицы A, размера n n, n = 1000, являются случайные числа, равномерно распределенные на интервале [ 1, 1].

Выполнить сингулярное разложение матрицы и построить график спектра сингулярных чисел. Будет ли матрица A близка к вырожденной? Как будут изменяться спектры сингулярных чисел при изменении интервалов равномерных распределений. Произвести аналогичные вычисления для матриц, элементами которой являются нормально распределенные случайные числа с некоторым стандартным отклонением 1.

сингулярного разложения матриц 1. На планете ZG5-V10 имеется горный массив, состоящий из потухших вулканов. Линейные размеры массива – (20 20) км. Рельеф поверхности этого массива описывается суперпозицией функций Гаусса где: wk – максимальная высота k -го вулкана, (u k, vk ) – координаты центров вулканов, d k – радиусы вулканов. Фотографический снимок этого горного массива в оцифрованном виде задан в виде матрицы H размера n n, n = 1000. Объем информации для хранения или передачи такого оцифрованного снимка I (h(ui, v j )) = 106 чисел. Цель задания – выяснить возможности сжатия объема информации без потери существенных деталей изображения горного массива.

Указания:

а) Задать набор чисел {wk, u k, vk, d k, k = 1, 2,..., 10}. Произвести дискретную выборку значений функции h(ui, v j ), i, j = 1, 2,..., n, n = 1000, и сформировать матрицу H, элементы которой hij = h(ui, v j ) ;

б) Выполнить сингулярное разложение матрицы H = USV T и построить график спектра сингулярных чисел i, i = 1, 2,..., n ;

в) Произвести обнуление сингулярных чисел i = 0, i = k + 1,..., n, и вычислить матрицу H = USV T. Матрица U, размера n k, такая, что k вектор-столбцов матрицы U совпадают с первыми k векторстолбцами матрицы U. S – матрица усеченных сингулярных чисел размера n k. Аналогично формируется матрица V. На основе визуального анализа графического изображения матриц H выяснить, при каких минимальных значениях k изображение горного массива можно считать удовлетворительным (т.е. достаточно точно локализуются координаты всех вулканов, отсутствуют артефакты в виде ложных вулканов и т.д.). Сравнить нормы Фробениуса матриц H и H (при удовлетворительном сжатом изображении горного массива);

г) Вычислить коэффициент максимально допустимого сжатия информации где: I (H ) – объем информации для хранения матрицы H, I (H ) – объем информации для хранения матрицы H.

д) Как измениться контрастность снимка, если где W – матрица “белого” шума, т.е. значениями элементов wij являются случайные числа с равномерным законом распределения?

Тема 4. Оптимальные параметры линейных математических моделей и оценка их доверительных радиусов Убедиться, что две серии экспериментальных данных, приведенных в таб. 1, являются эквивалентными в смысле МНК для линейной математической модели Указания:

а) Сформировать матрицу плана F, размера 21 3, следующего вида Компоненты векторов t, f e,1 и f e, 2 взять из таб. 1;

б) Вычислить и сравнить векторы оптимальных параметров для двух серий экспериментальных данных f e,1 и f e, 2 по формуле в) Оценить длины векторов погрешностей в двух сериях измерений и вычислить радиусы доверительной области векторов оптимальных параметров по формуле функционала МНК в оптимальных точках p opt, i.

2) Для экспериментальных данных, приведенных в таб. 1, (n = 1, 2, 3), вычислить оптимальные параметры модели после каждого усреднения и сравнить результаты. Скользящее усреднение проводить по двум соседним точкам.

3) Вычислить две серии эквивалентных “ экспериментальных ” данных для линейной математической модели Указания:

а) Задать векторы p = ( p1, p2,..., p5 )T и t = (t1, t 2,..., t n )T ;

б) Сформировать матрицу плана F, вычислить вектор значений f ;

в) Сформировать два вектора погрешностей 1f и 2f с помощью датчика случайных чисел, распределенных по нормальному закону с различными дисперсиями. Разложить эти векторы на ортогональные составляющие где г) Сформировать два вектора: f1 = (f + 1, r f ) + 1, 0f, Убедиться, что эти векторы являются эквивалентными в смысле определения оптимальных параметров по МНК. Можно ли на основе визуального анализа графиков отдать предпочтение одной из серий “экспериментальных” измерений – t j, f1 (t j ) или t j, f2 (t j ) ?

Тема 5. Аппроксимация функций 1. С помощью многочленов степени k, k = 5, 6, аппроксимировать функции:

г) f 4 ( x), f 5 ( x), … – выбрать самостоятельно.

2. Аппроксимировать выше упомянутые функции тригонометрическими многочленами Tk (x), k = 5, 6 и сравнить результаты.

Тема 6. Численное решение интегрального уравнения свертки вычислить свертку Произвести дискретную выборку с некоторым постоянным шагом значений функций f (t ) и h(t ) (объем выборки n > 100 ) и образовать векторы f и h. Сформировать матрицу дискретной свертки H и вычислить свертку g = H1f. Вычислить f sol = H1+ g и сравнить с вектором f и функцией f (t ). Провести анализ спектра сингулярных чисел матрицы H1 и применить процедуру пороговой модификации малых сингулярных чисел с целью получения приближенных решений fsol = H1+ g.

Примечание. Функции f (t ) и h(t ) каждый исполнитель выбирает самостоятельно.

Тема 7. Приближенное решение плохо-обусловленных систем линейных уравнений большого порядка Указания:

1. Для матрицы H, рассматриваемой в Теме 3, провести анализ спектра сингулярных чисел.

2. Сформировать вектор с компонентами v j = hij, j = 1, 2,..., n.

Номер строки i должен соответствовать наиболее выразительному одномерному сечению функции h(u, v). Вычислить:

принадлежали ранговым пространствам R (H T ) и R (H ), соответственно. Тогда решением системы Hv = u 2, r будет вектор v = v r = H + u 2, r. Однако, если в спектре сингулярных чисел наблюдается “нырок” к очень малым числам, то необходимо проводить пороговую модификацию сингулярных чисел и вычислять приближенные решения.

4. Проводя серию пороговой модификации спектра сингулярных чисел матрицы H, вычислить 5. Сравнить графики дискретных функций j, vr, j и {j, vopt, app, j }, где j – номер компоненты векторов v r и v opt, app.

1. Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. – М.: Мир, 1969.

2. Лоусон Ч., Хенсон Р. Численное решение задач метода наименьших квадратов. – М.: Наука, 1986.

3. Голуб Дж., Ван Лоун Ч. Матричные вычисления. – М.: Мир, 1999.

4. Деммель Дж. Вычислительная линейная алгебра. Теория и приложения. – М.: Мир, 2001.

§1. Основная теорема линейной алгебры ………………………. §2. Сингулярное разложение матриц ……………………………. §3. Спектральная классификация матриц произвольного размера и критерии плохой обусловленности …………………………. §4. Линейные математические модели: оптимальные параметры и радиусы доверительной области.…………………………… §5. Алгоритмы численного решения интегрального уравнения §6. Задания специального вычислительного практикума ……… Рекомендуемая литература …………………………………….. АНДРУШЕВСКИЙ Николай Матвеевич систем линейных алгебраических уравнений специального вычислительного практикума Факультета вычислительной математики и кибернетики 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, Напечатано с готового оригинал-макета Формат 60х90 1/16. Усл.печ.л. 4,38. Тираж 100 экз. Заказ 659.

119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова,

Похожие работы:

«Санкт-Петербургский государственный университет факультет социологии кафедра экономической социологии А. В. Петров Международная организация труда Учебно-методическое пособие Санкт-Петербург Астерион 2007 ББК 60.5 П 31 Материалы учебно-методического пособия подготовлены при поддержке РФФИ (проект № 06-06-80311-а) Утверждено на заседании ученого совета факультета социологии Санкт-Петербургского государственного университета Автор-составитель: доктор социологических наук А. В. Петров Рецензенты:...»

«Федеральная таможенная служба Государственное казенное образовательное учреждение высшего профессионального образования Российская таможенная академия Владивостокский филиал Утверждено решением учебно-методического совета факультета таможенного дела Владивостокского филиала Российской таможенной академии протокол № 8 от 23.12.2011 МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ ВЫПУСКНЫХ КВАЛИФИКАЦИОННЫХ РАБОТ для студентов специальности 080115.65 Таможенное дело специализации Таможенная логистика...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ АЛТАЙСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ Рассмотрено и одобрено Утверждаю: на заседании ученого совета Ректор университета 23 декабря 2008 г. Протокол № 4 _ С.В. Золотарев 24 декабря 2008 г. ОТЧЕТ о результатах самообследования деятельности Алтайского государственного аграрного университета (АГАУ) за 2004-2008 гг. Барнаул 2008 Содержание Общие...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Технологический институт Федерального государственного образовательного учреждения высшего профессионального образования Южный федеральный университет СОГЛАСОВАНО УТВЕРЖДАЮ Зав. кафедорой РТС Декан радиотехнического факультета _ В. Т. Лобач _ С. Г. Грищенко 200/ учеб.год _200/_ учеб.год УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС (УМК) учебной дисциплины ПРОЕКТИРОВАНИЕ УСТРОЙСТВ ОБРАБОТКИ СИГНАЛОВ Таганрог 2008 г. 1....»

«2 3. Ротач В.Я. Теория автоматического управления: учебник для вузов. – 2-е изд., перераб. и доп.– М.: Издательство МЭИ, 2004. Метрология, стандартизация и сертификация. 1.Общие вопросы стандартизации и сертификации. Основные понятия и определения в области стандартизации: цели и задачи стандартизации; нормативные документы, используемые в области стандартизации. 2. Стандартизация и сертификация. Термины и определения, относящиеся к качеству продукции: основные понятия в области сертификации;...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ НЕФТИ И ГАЗА им. И.М. ГУБКИНА УНЦ ГАЗОХИМИЯ ИОХ им. Н.Д.ЗЕЛИНСКОГО РАН – РГУ НЕФТИ И ГАЗА им. И.М. ГУБКИНА В.С.Арутюнов, А.Л.Лапидус ВВЕДЕНИЕ В ГАЗОХИМИЮ МОСКВА-2004 УДК 622.276.53 Г 13 Арутюнов В.С., Лапидус А.Л. Введение в газохимию. Учебное пособие. Учебное пособие является вводной частью цикла Основы газохимии. В нем рассматривается значение природных газов в экономике и энергетике, генезис и...»

«Министерство транспорта Российской Федерации Федеральное агентство железнодорожного транспорта ГОУ ВПО Дальневосточный государственный университет путей сообщения Кафедра Экономика транспорта В.В. Комарова О.Б. Кадурова ЦЕНООБРАЗОВАНИЕ НА ТРАНСПОРТЕ Рекомендовано Методическим советом в качестве учебного пособия Хабаровск Издательство ДВГУПС 2006 УДК 338.47:656.2(075.8) ББК У9(2)372.1я73 К 630 Рецензенты: Кафедра Экономика транспорта Самарского государственного университета путей сообщения...»

«ББК 32.973.26-018.1 Д 21 Д 21 Даулеткулов А.Б. Олимпиады по информатике: Учебно-методическое пособие. -Алматы: ИНТ, 2004 - 242 c. ISBN 9965-9293-5-1 Олимпиады по информатике среди школьников проводятся с середины 80-х годов. С начала 90-х годов основными условиями победы на олимпиадах по информатике принято считать успешную отладку на ЭВМ программ, решающих конкурсные задачи. Книга ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ состоит из трех частей. В первой части приведены задачи международных, республиканских и...»

«Методическое объединение вузовских библиотек Алтайского края Вузовские библиотеки Алтайского края Сборник Выпуск 10 Барнаул 2010 ББК 78.34 (253.7)657.1 В 883 Редакционная коллегия: Л. В. Бобрицкая, И. Н. Кипа, Н. Г. Шелайкина, Е. А. Эдель, Т. А. Мозес Л. А. Божевольная. Гл. редактор: Н. Г. Шелайкина Отв. за выпуск: М. А. Куверина Компьютерный набор: Л. Н. Вагина Вузовские библиотеки Алтайского края: сборник: Вып. 10. /Метод. объединение вуз. библиотек Алт. края. – Барнаул: Изд-во АлтГТУ, 2010....»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТУРИЗМА И СЕРВИСА (ФГБОУ ВПО РГУТиС) Институт туризма и гостеприимства (г.Москва) филиал Кафедра организации и технологии в туризме и гостиничной деятельности ДИПЛОМНАЯ РАБОТА на тему: Разработка рекомендаций по развитию безбарьерного туризма на примере города Сочи по специальности: 100103.65...»

«Томский межвузовский центр дистанционного образования М.А. Афонасова МЕНЕДЖМЕНТ Учебное пособие ТОМСК – 2005 Федеральное агентство по образованию ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР) Кафедра экономики М.А. Афонасова МЕНЕДЖМЕНТ Учебное пособие Допущено Советом Учебно-методического объединения вузов России по образованию в области менеджмента в качестве учебного пособия 2005 Корректор: Воронина М.А. Афонасова М.А. Менеджмент: Учебное пособие. Томск:...»

«Министерство образования и науки Российской Федерации Государственное образовательное учреждение высшего профессионального образования Тамбовский государственный технический университет ГРАЖДАНСКАЯ ОБОРОНА И ЗАЩИТА ОТ ЧРЕЗВЫЧАЙНЫХ СИТУАЦИЙ Методические указания Тамбов Издательство ТГТУ 2005 ББК Ц69я73-5 Е302 Утверждено Редакционно-издательским советом университета. Рецензент Доктор технических наук, профессор Н. С. Попов Е302 Гражданская оборона и защита от чрезвычайных ситуаций: Метод. указ. /...»

«МИНИСТЕРСТВО КУРОРТОВ И ТУРИЗМА КРЫМА КРЫМСКАЯ АССОЦИАЦИЯ СЕЛЬСКОГО ЗЕЛЕНОГО ТУРИЗМА ЮЖНЫЙ ФИЛИАЛ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ БИОРЕСУРСОВ И ПРИРОДОПОЛЬЗОВАНИЯ УКРАИНЫ КРЫМСКИЙ АГРОТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ Информационно-консультационный центр ОРГАНИЗАЦИОННО-ПРАВОВЫЕ ВОПРОСЫ РАЗВИТИЯ СЕЛЬСКОГО ЗЕЛЕНОГО ТУРИЗМА Симферополь, 2008 Методические указания Организационно-правовые вопросы развития сельского зеленого туризма разработаны в соответствии с заказом Министерства курортов и туризма Крыма....»

«РОССИЙСКАЯ ФЕДЕРАЦИЯ МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНСТИТУТ ГОСУДАРСТВА И ПРАВА МЕТОДИЧЕСКИЕ УКАЗАНИЯ по оформлению контрольных работ, курсовых работ, выпускных квалификационных работ, магистерских диссертаций для студентов Института государства и права Тюмень 2013 1 Настоящие методические указания подготовлены на основе следующих нормативно-технических...»

«Министерство образования Российской Федерации Ульяновский государственный технический университет СИСТЕМЫ АВТОМАТИЧЕСКОГО УПРАВЛЕНИЯ Методические указания по курсовому проектированию Ульяновск 2002 Министерство образования Российской Федерации Ульяновский государственный технический университет СИСТЕМЫ АВТОМАТИЧЕСКОГО УПРАВЛЕНИЯ Методические указания по курсовому проектированию Составитель М. А. Цветов Ульяновск 2002 УДК 681. 5 (076) ББК 32. 96я7 С 40 Рецензент канд. техн. наук, доцент кафедры...»

«ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ – ВЫСШАЯ ШКОЛА ЭКОНОМИКИ Санкт-Петербургский филиал КАФЕДРА ГОСУДАРСТВЕННОГО И МУНИЦИПАЛЬНОГО УПРАВЛЕНИЯ Методические указания по подготовке и защите дипломных работ ИЗДАТЕЛЬСТВО СПб ФИЛИАЛ ГУ-ВШЭ 2007 УДК37 ББК Кайсарова В.П., к.э.н., доцент СПб филиал ГУ-ВШЭ, Санина А.Г., к.с.н., ст. преподаватель Методические указания по подготовке и защите дипломных работ Рецензенты: Ходачек А.М., д.э.н., профессор, зав.кафедрой государственного и муниципального управления...»

«РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ ИММАНУИЛА КАНТА С. В. Мациевский ВЫСШАЯ МАТЕМАТИКА ДЛЯ ГУМАНИТАРИЕВ Учебное пособие Издательство Российского государственного университета им. И. Канта 2010 УДК 51(075) ББК 22.11я73 М 367 Рецензенты: доцент кафедры высшей математики КГТУ канд. физ.-мат. наук А. А. Юрова Мациевский С. В. М 367 Высшая математика для гуманитариев: учебное пособие.— Калининград: Изд-во РГУ им. И. Канта, 2010.— 299 с.: ил., табл. ISBN 978-5-9971-0040- Это учебное пособие...»

«ВЫСШЕЕ ОБРАЗОВАНИЕ серия основана в 1996 г. Московская государственная юридическая академия Е.П. ИЩЕНКО А.А. ТОПОРКОВ КРИМИНАЛИСТИКА УЧЕБНИК Издание второе, исправленное и дополненное Под редакцией доктора юридических наук, профессора Е.П. Ищенко Допущено Министерством образования Российской Федерации в качестве учебника для студентов высших учебных заведений, обучающихся по специальности 021100 Юриспруденция Юридическая фирма Издательский Дом КОНТРАКТ ИНФРА-М Москва, 2006 УДК 343.98(075.8) ББК...»

«Министерство образования и науки Российской Федерации Самарский государственный университет Утверждаю: Ректор И.А. Носков _30 июня_2011_ г. Основная образовательная программа высшего профессионального образования Направление подготовки 020100 -Химия Квалификация Магистр химии Самара 2011 г. 1. Общие положения 1.1. Примерная основная образовательная программа высшего профессионального образования (ПООП ВПО) подготовки магистров по направлению 020100.68 - Химия Примерная основная образовательная...»

«И. А. Зенин Гражданское и торговое право зарубежных стран УЧЕБНОЕ ПОСОБИЕ 2-е издание, переработанное и дополненное МОСКВА • ЮРАЙТ • 2011 УДК 34.7 ББК 67.404я73 З56 Автор: Зенин Иван Александрович — заслуженный профессор МГУ им. М. В. Ломоносова, доктор юридических наук, профессор, член Международной ассоциации интеллектуальной собственности (ATRIP — Женева, Швейцария), арбитр Международного коммерческого арбитражного суда при Торговопромышленной палате РФ. Рецензент: Телицын В. М. — кандидат...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.