Задача численного решения линейных систем; нормы векторов и матриц

ЛЕКЦИЯ 10.1 ЗАДАЧА ЧИСЛЕННОГО РЕШЕНИЯ ЛИНЕЙНЫХ СИСТЕМ. НОРМЫ ВЕКТОРОВ И МАТРИЦ. ПРЯМЫЕ МЕТОДЫ Эта лекция начинает блок, посвящѐнный численным методам линейной алгебры. Напомним, что линейная алгебра – это раздел алгебры, в котором исследуются линейные объекты: векторные (или линейные) пространства, линейные отображения, системы линейных алгебраических уравнений. Основной математический аппарат, используемый в линейной алгебре — матрицы. Соответственно, численные методы линейной алгебры – методы численного решения матричных задач. Наиболее важными из них являются решение систем линейных алгебраических уравнений и проблема собственных значений. Ими мы и займѐмся в этой части нашего курса. 1. Постановка задачи численного решения систем линейных уравнений Дана система линейных алгебраических уравнений { или в матричном виде где )― ( матрица системы, ( ) ― вектор неизвестных, При условии невырожденности матрицы ( ( ) ― вектор правой части. ) система имеет единственное ре- шение . Задача состоит в том, чтобы вычислить приближѐнное решение -1- . Существуют точные и приближенные методы еѐ решения. Например, к точным методам относятся метод Гаусса, метод обратной матрицы, формулы Крамера. Эти методы имеют большую вычислительную сложность. Например, число умножений при вычислении определителей в методе Крамера равно , что очень велико при . При таком коли- честве арифметических операций быстро накапливаются погрешности округлений, и решение является неустойчивым по отношению к возмущениям матрицы и правой части. В методе Гаусса тоже большое количество операций. При практичнее решать систему приближенными методами, учитывающими те или иные их особенности матрицы. Задача численного решения линейных систем чрезвычайно актуальна. Исследование применения численных методов показало, что примерно 75% всех вычислений приходится на решение систем линейных алгебраических уравнений. Причем, число неизвестных может достигать нескольких сотен или тысяч. Поэтому математикам, разрабатывающим приближенные методы решения СЛАУ, надо изобретать все более эффективные методы. 2. Числовые характеристики приближѐнного решения. Нормы векторов и матриц 2.1. Погрешность и невязка приближѐнного решения Понятно, что численное решение задачи подразумевает не только нахождение приближѐнного решения, но и оценку погрешности. Качество приближѐнного решения определяется свойствами разности решения . Этот вектор будем называть погрешностью : . является еѐ невязка Другой характеристикой приближѐнного решения . Очевидно выводится связь между погрешностью и невязкой: ( -2- ) . Прежде чем приступать к рассмотрению методов нахождения лярную величину, характеризующую степень близости векторов , надо определить скаи , т.е. погрешность . Для одномерных числовых величин абсолютная погрешность определяется как модуль. В многомерном случае аналогами модуля являются нормы векторов и матриц. 2.2. Нормы векторов и матриц Пусть ной нормой в ― пространство числовых векторов размерности называется числовая функция (n-векторов). Вектор― неотри- , где цательная числовая полуось, удовлетворяющая условиям: 1) 2) 3) , | | ― нулевой вектор; для любого действительного числа для любых , Норма произвольного вектора и любого ; (неравенство треугольника). обозначается ‖ ‖, т.е. ‖ ‖. По свойствам нормы видно, что она численно характеризует величину, или «длину», вектора. Чем она больше, тем более отличен вектор (по совокупности координат) от нулевого. Поэтому норму логично взять в качестве характеристики величины погрешности. Итак, абсолютной погрешностью приближѐнного решения ‖ называется норма вектора ‖ ‖ ‖. Как и в случае с абсолютной погрешностью скалярной величины, вить невозможно. Вместо неѐ находится еѐ верхняя оценка Безразмерной характеристикой : точно устано- . является относительная погрешность ‖ ‖ ‖ ‖ ‖ ‖ Эта величина также не поддаѐтся вычислению, вместо неѐ определяется верхняя оценка . В вычислительной математике наиболее употребительными являются следующие нормы: ‖ ‖ , ‖ ‖ , ‖ ‖ . Первая (читается «норма-один», другое название ― октаэдриче- ская норма) вычисляется по формуле -3- ‖ ‖ ∑| | Вторая ― евклидова норма («норма-два», или сферическая): ‖ ‖ √∑ В двумерном и трѐхмерном пространствах она совпадает с евклидовой длиной вектора. Последняя норма («норма-бесконечность», кубическая норма) вычисляется формулой ‖ ‖ | | Для всех трѐх легко доказываются свойства 1) - 3) нормы. Кроме того, они связаны очевидными неравенствами ‖ ‖ ‖ ‖ ‖ ‖ ‖ ‖ Выбор той или иной нормы определяется предъявляемыми к решению требованиями. Например, евклидову норму применяют тогда, когда нужно минимизировать среднеквадратическую ошибку решения, ‖ ‖ ― если минимальной должна быть максимальная из погрешностей переменных , . Для формулировок условий сходимости итерационных методов и понятия устойчивости решения по отношению к возмущениям коэффициентов системы потребуется аналогичная числовая величина для матриц. Она называется матричной нормой. Пусть пространство числовых квадратных матриц размерности называется числовая функция 1) 2) | | 3) 4) Норма матрицы . Нормой матрицы , удовлетворяющая условиям: , пространства ― ― нулевая матрица размерности (нулевой элемент ); для любого действительного числа для любых , для любых , и любой ; (неравенство треугольника); . обозначается так же, как и векторная: ‖ ‖. Матричную норму можно определить бесконечным множеством способов. Так как в вычислительных задачах линейной алгебры требуется оценивать и векторы, и матрицы, то целесообразно вводить норму так, чтобы она разумным образом была связана с применяющейся вектор-4- ной нормой. Именно, будем говорить, что матричная норма согласована с данной векторной, если ‖ для любых и ‖ ‖ ‖ ‖ ‖ . Особое значение при оценках имеет наименьшая норма мат- рицы, согласованная с данной векторной. Из (6) очевидно следует, что она равна максимуму отношения норм векторов и при всех ненулевых : ‖ ‖ ‖ ‖ ‖ ‖ Эту норму называют подчинѐнной соответствующей векторной. Можно показать, что еѐ можно вычислять как максимум норм на единичной сфере ‖ ‖ ‖ ‖ ‖ : ‖ ‖ ‖ Именно подчинѐнная норма, наименьшая из всех согласованных, определѐнная формулой (7), применяется при оценках матриц. Приведѐм без доказательства формулы матричных норм, подчинѐнных введѐнным выше векторным. Норме (2) подчинена матричная норма ‖ ‖ ∑| | норме (3) ― ⁄ ‖ ‖ где ( ) ― собственные числа матрицы (она является эрмитовой, следовательно, неотрицательно определѐнной, поэтому все еѐ собственные числа вещественны и неотрицательны). Эту норму называют спектральной, или верхней гранью матрицы. Кубической норме (4) подчинена ‖ ‖ ∑| | Нормы ‖ ‖ и ‖ ‖ связаны неравенством ‖ ‖ ‖ ‖ -5- ‖ ‖ Пример. Вычислить нормы матрицы ( ). Собственные числа данной матрицы √ : и ; поэтому ⁄ ‖ ‖ ( ) √ √ Остальные нормы вычисляются совсем просто: ‖ ‖ ∑| | ‖ ‖ ∑| | 3. Прямые методы В прямых методах точное (без учѐта вычислительных погрешностей) решение достигается за конечное число шагов. Число необходимых арифметических операций в них зависит только от вычислительной схемы и порядка матрицы системы. 3.1. Метод Гаусса Этот простой и естественный метод основан на последовательном исключении переменных. Он имеет несколько вычислительных схем. Здесь будет рассмотрена только схема единственного деления. Алгоритм метода Гаусса состоит из прямого и обратного хода. На первом матрица системы приводится к треугольному виду, на втором ― вычисляются значения переменных, начиная с последнего. Итак, начнѐм описание алгоритма с прямого хода. Дана система (1) с невырожденной матрицей (для большей наглядности она записана в развѐрнутом виде): { -6- Опишем первый шаг прямого хода. Пусть . Если это условие не выполняется, то перестановкой уравнений (соответственно, строк матрицы) или переименованием переменных (перестановкой столбцов) можно добиться того, чтобы на месте ненулевой коэффициент. Число оказался называется ведущим элементом первого шага. Снача- ла вычисляются коэффициенты , . Затем i-е уравнение ( умноженным на , ) заменяется разностью между ним и первым, . Первое уравнение остаѐтся неизменным. В результате получается си- стема { где , менная , , , , , , , у которой пере- исключена из второго, третьего и т.д. уравнений. Таким образом, происходит последовательное исключение переменных. Ниже приведены вид системы в результате выполнения k-го шага и расчѐтные формулы: { где , , , После , , , ; ― ведущий элемент. -го шага система приводится к треугольному виду: -7- , { На этом прямой ход метода Гаусса закончен. На обратном ходе вычисляются значения переменных. Из последнего уравнения находим : ). Далее, из предпоследнего ― (если матрица системы невырожденная, то ( ( как ведущий элемент : ) -го шага). Продолжая двигаться по системе в обратном направлении, получаем значения всех переменных. Общая расчѐтная формула: ( , 1; ) вычисляется по формуле (9). Число арифметических операций на прямом ходе метода Гаусса равно примерно , или , на обратном ― . Поэтому при больших вычислительная сложность обратного хода пренебрежимо мала по сравнению с прямым. Заметим, что если на каком-то шаге ведущий элемент оказывается близким к нулю, то деление на него, чего требуют алгоритмы обоих ходов, может привести к большим погрешностям. В этом случае применяют другие вычислительные схемы, например, частичного или полного выбора. Преимущества метода Гаусса заключаются в его простоте и универсальности: он применим для любых матриц. Однако в этом кроется и его недостаток: он никак не использует структуру матрицы, поэтому для матриц специального вида (разреженных, треугольных или близких к ним) вычислительная сложность та же, что и для матриц общего вида. Кроме того, метод Гаусса применим для систем линейных уравнений и тогда, когда -8- она может иметь и бесконечно много решений или не иметь решений. Применяя к системе все шаги прямого хода, получаем равносильную систему, по треугольному виду которой можно судить о числе решений. Для систем со специальными матрицами лучше применять методы, разработанные под них. Одним из них является метод прогонки. Пример. Исследовать методом Гаусса систему { Приводим систему к равносильному виду { { { Система пяти уравнений с тремя неизвестными имеет единственное решение , . Пример. Рассмотрим еще один пример: { Методом исключения систему можно привести к виду { Решение не единственное: -9- , , , . Пример. Можно также привести пример системы, не имеющей решения: { Система равносильна следующей: { Система не имеет решения. 3.2. Метод прогонки Метод прогонки разработан для трѐхдиагональных систем вида { Матрица системы (10) имеет специальную трѐхдиагональную структуру: ( ) Такие системы возникают при численном решении задач математической физики, интерполяции сплайнами и во многих других случаях. Метод прогонки состоит из прямого и обратного ходов. На прямом вычисляются прогоночные коэффициенты. Опишем по шагам этот процесс. На первом шаге в первом уравнении (10) - 10 - выражается через : где прогоночные коэффициенты первого шага. На втором шаге подставляется во второе уравнение, откуда находится через : где прогоночные коэффициенты второго шага. Таким же образом вычисляются все остальные коэффициенты. В результате i-го шага получаем следующие формулы: где На последнем, n-м, шаге найденное ранее значение подставляется в последнее уравнение (10) и определяется : Приведѐм общую сводку формул прогоночных коэффициентов в наиболее удобном для программной реализации виде: - 11 - На обратном ходе вычисляются переменные начиная с последнего: , , по рекуррентным формулам (11), , ,…, . Вычислительная сложность алгоритма метода прогонки составляет , что гораз- до меньше, чем у метода Гаусса. Кроме того, трѐхдиагональная структура матрицы позволяет использовать для еѐ хранения только машинных слова. Очевидно, что этот алгоритм осуществим только тогда, когда все , и для меньших погрешностей желательно, чтобы они не были слишком близки к нулю. Достаточные условия для этого формулируются следующей теоремой. Теорема 1. Пусть коэффициенты системы (10) удовлетворяют условиям диагонального преобладания: | | | | | |, причѐм , , . Тогда и| | для всех , . Условия диагонального преобладания гарантируют не только применимость метода прогонки, но и его устойчивость к возмущениям матрицы системы. - 12 -