Корректность. Аппроксимация.

В.Н. КРИЗСКИЙ

ЧИСЛЕННЫЕ МЕТОДЫ
ЛИНЕЙНОЙ АЛГЕБРЫ

Учебно-методическое пособие

Стерлитамак – 2006

УДК

ББК

Кризский В.Н. Численные методы линейной алгебры: Учебно-методическое пособие / Изд-во Стерлитамакской госпедакадемии – Стерлитамак, 2006 –?? с.

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

Пособие предназначено для студентов ВУЗов, обучающихся по специальностям «Прикладная математика и информатика», «Математическое обеспечение и администрирование информационных систем», но также выборочно может быть использовано при изучении курса «Численные методы» студентами физико-математических специальностей вузов, поскольку опирается на знания стандартных курсов математического анализа и линейной алгебры.

Рецензенты:

кафедра вычислительной математики
Башкирского государственного университета, г. Уфа
(зав.кафедрой – д.ф.-м.н, проф. Н.Д. Морозкин)

д.ф.-м.н., проф. С.И. Спивак (кафедра математического моделирования БашГУ, г.Уфа);

д.ф.-м.н., проф. И.А. Калиев (кафедра математического анализа СГПА, г. Стерлитамак);

ISBN

ВВЕДЕНИЕ

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

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

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

В пособии рассмотрены широко используемые на практике методы решения задач линейной алгебры: определения важных характеристик матриц (и связанных с ними преобразований конечномерных линейных пространств) – определителя, собственных значений и векторов (собственных линеалов), нормы, числа обусловленности; разложения матриц; решения систем линейных алгебраических уравнений (СЛАУ). Обсуждаются вопросы корректности задач решения СЛАУ.

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

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

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

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

В.Н. Кризский

ПРОГРАММА

Корректность. Аппроксимация.

Операторное уравнение. Корректность задач по Адамару. Корректность задач по Тихонову. Аппроксимация, сходимость, устойчивость. Изоморфизм пространства линейных операторов в конечномерных пространствах пространству матриц.

ОСНОВНЫЕ ПОНЯТИЯ ВЕКТОРНЫХ, МЕТРИЧЕСКИХ И НОРМИРОВАННЫХ ПРОСТРАНСТВ

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

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

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

1) тогда и только тогда, когда ;

2) для любых ;

3) для любых (неравенство треугольника).

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

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

Любая сходящаяся последовательность метрического пространства – фундаментальна (обратное не всегда верно).

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

Множество называется линейным (векторным) пространством, если в нем определены операции сложения (+) элементов и умножения (∙ ) элемента на число, не выводящие за пределы и удовлетворяющие следующим аксиомам:

1) сложение ассоциативно: ;

2) сложение коммутативно: ;

3) существует нейтральный по отношению к операции сложения (нулевой) элемент , такой что ;

4) ;

5) и ;

6) и ;

7) и ;

8) .

Система элементов линейного пространства называется линейно зависимой, если существуют такие числа одновременно не равные нулю, что . Если это равенство выполняется только при , то система называется линейно независимой.

Множество называется линейным нормированным пространством, если – линейное пространство, на котором определен вещественный функционал , т.е. каждому поставлено в соответствие вещественное число , называемое нормой и удовлетворяющее аксиомам:

1) , причем тогда и только тогда, когда ;

2) , ;

3) , .

Элемент называется нормированным, если .

Линейное нормированное пространство – есть частный случай метрического пространства, в котором норма определена метрикой.

Полное линейное нормированное пространство называется банаховым.

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

1) , причем тогда и только тогда, когда ;

2) , ;

2) и , .

Элементы называются ортогональными, если . Ортогональность элементов обозначается так: .

Если в линейном пространстве определено скалярное произведение, то в нем можно определить норму и расстояние (квадратичную метрику) . Метрическое пространство, с метрикой, простроенной на основе скалярного произведения называется предгильбертовым или унитарным.

Полное унитарное пространство называется гильбертовым.

Если в унитарном пространстве последовательность сходится, т.е , то .

Если в унитарном пространстве последовательность фундаментальна, то последовательность соответствующих норм сходится.

Если в унитарном пространстве последовательность фундаментальна, то она ограничена, т.е. , .

Оператор называется линейным, если он определен на линейном пространстве и является аддитивным и однородным:

1) , (аддитивность);

2) (однородность).

Множество значений линейного оператора линейно.

Если для линейного оператора существует обратный оператор , то – линейный оператор.

Пусть – метрическое пространство. Оператор называется сжимающим, если существует такое число , что для .

(Банаха о неподвижной точке) (Принцип сжимающих отображений)

Пусть – сжимающий оператор в полном метрическом пространстве , тогда уравнение в этом пространстве имеет одно и только одно решение (т.е. ). Элемент может быть получен как предел последовательности с произвольным начальным членом .

Оператор называется ограниченным в , если , . Наименьшее из таких констант называется нормой оператора.

Оператор называется непрерывным в точке , если для любой последовательности элементов для которой , последовательность сходится к , т.е. или . Если оператор непрерывен во всех точках , то говорят, что он непрерывен в .

Пусть – линейный оператор в гильбертовом пространстве . Если он ограничен в , то он так же и непрерывен в .

КОРРЕКТНОСТЬ. АППРОКСИМАЦИЯ

«… вся наука подчинена идее
аппроксимации …»

Б. Рассел

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

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

Точность метода связана с затратами ресурсов вычислительной системы. Повышение точности, как правило ведет к повышению времени работы системы и к увеличению требуемого объема памяти. Эффективность метода в свою очередь зависит от мощности множества задач, к которым может данный метод быть применен. Чем шире класс решаемых данным методом задач, следовательно, чем метод универсальнее, тем метод менее эффективен. Найдется такая задача в классе, на которой метод будет давать плохие показатели времени, величины погрешности и т.п. И обратно, сужение класса решаемых задач позволяет модифицировать метод с учетом дополнительных свойств и ограничений, повысив его эффективность. Универсальность метода при этом теряется, метод становится узкоспециальным. «Что-либо приобретая, мы что-то теряем» – эта общая философская сентенция четко работает и в курсе «Численных методов».

Любая исходная задача на языке теории операторов может быть описана следующим образом

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

Если оператор известен и элемент известен, то говорят, что имеет место прямая задача поиска элемента по элементу .

Например: Пусть – пространство прямоугольных матриц, – подмножество квадратных матриц, – есть правило нахождения определителя матрицы, тогда для каждой квадратной матрицы можно найти число . Таким образом, нахождение определителя квадратной матрицы – есть прямая задача.

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

Задача

(1)

называется корректной или корректно поставленной по Адамару, на паре метрических пространств , если выполняются условия существования, единственности и устойчивости решения:

1) для любого существует решение ;

2) это решение единственно;

3) решение устойчиво, т.е. для любой сходящейся к в метрике пространства последовательности элементов последовательность будет сходится к в метрике пространства . Это означает, что обратный оператор непрерывен.

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

Корректность задачи напрямую связана с выбором пространств и метрик в них, а также множеств и (с ограничениями на искомые решения). Задача может быть корректна на одной паре пространств и не являться корректной на другой паре. Очевидно, что при расширении пространства , может оказаться, что не для любого решение задачи (1) может существовать. Если оператор линеен, а пространства – банаховы, то для корректности задачи необходимо и достаточно существование ограниченного обратного оператора из в , причем с областью определения, совпадающей с пространством .

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

с невырожденной ( ) матрицей.

Ее решение очевидно находится: . Изменим в системе правую часть первого уравнения на 0.1, получив систему вида

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

Приведем еще два примера, когда решение задачи не существует (не выполняется условие 1 определения корректности по Адамару) и когда оно существует, но не является единственным (не выполняется условие 2).

Первому случаю соответствует, например, СЛАУ вида

Здесь решения нет в соответствии с теоремой Кронекера-Капелли, поскольку ранг матрицы не равен рангу расширенной матрицы.

Второму случаю соответствует система вида

Здесь бесконечное множество решений вида , где выступает в роли параметра.

Ранее считалось, что некорректные задачи не имеют физического смысла, и поэтому их не рассматривали. Однако развитие прикладных наук показывает, что многие важные задачи практики являются по Адамару некорректно поставленными. А.Н. Тихоновым было предложено новое понятие корректности, которое является физически оправданным для многих некорректных по Адамару задач. Рассматривается существенно более узкое, чем все пространство , множество . Пусть образ множества при отображении – есть множество .

Задача (1) называется условно корректной или корректной по Тихонову, если для нее выполнены следующие условия:

1) известно априори, что решение задачи существует и принадлежит некоторому заданному множеству ;

2) решение задачи единственно на множестве ;

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

Множество называется множеством корректности задачи.

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

Заметим, что в условно-корректных задачах нет необходимости доказывать теорему единственности решения задачи (1), т.к. постулируется, что решение на некотором множестве существует.

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

Некоторые некорректные по Адамару задачи являются корректными по Тихонову.

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

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

Рис.2. Аппроксимация задачи.

Связь между пространствами и будем определять оператором , а между пространствами и – оператором . Операторы и называются операторами сноса. Оператор назовем оператором восполнения (см. рис. 2.). В общем случае оператор не является обратным оператору ( ). Уравнение заменяется на уравнение . (2)

Предположим, что его решение – – единственно. Так как и не принадлежит пространству , то, следовательно, мы не вправе называть приближенным решением исходного уравнения (1). Будем называть его каркасом приближенного решения. Приближенным решением уравнения (1) будем называть элемент . Отметим, что элемент может и не принадлежать области задания оператора .

Если обозначить точное решение уравнения (1) через , то можно в метрике пространства измерить расстояние между точным и приближенным решением. Говорят, что имеет место сходимость приближенных решений, если . Можно также рассматривать расстояние между каркасом приближенного решения и сносом в пространство точного решения – величину . Если , то говорят, что имеет место сходимость каркасов приближенных решений.

Рис.3. Погрешность аппроксимации.

Говорить о сходимости приближенных решений можно лишь тогда, когда уравнение (2) аппроксимирует уравнение (1). Уравнение (2) аппроксимирует уравнение (1) (оператор аппроксимирует оператор ), если погрешность аппроксимации стремиться к нулю при .

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

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

Методы решения задачи делятся на следующие основные классы: 1) методы точные, в которых точное решение задачи определяется за конечное число шагов в предположении отсутствия ошибок округления; 2) методы итерационные, в которых точное решение может быть найдено лишь как результат бесконечной итерационной процедуры, которая представляет собой правило определения последующего приближения на основе нескольких ранее вычисленных приближений; 3) методы вероятностные, в которых задействован аппарат теории вероятности и решение задачи – есть величина, для которой определена лишь вероятность ее попадания в окрестность точного решения.

Точные методы, как правило, применяются для задач небольших размерностей ( ), итерационные – для задач размерности , вероятностные для задач больших размерностей ( ).

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

Линейный оператор однозначно связан с матрицей. В [1] показано, что матрица определяет линейный оператор и линейный оператор определяет матрицу. Это соответствие сохраняется при действиях над операторами: матрица суммы операторов равна сумме матриц слагаемых и матрица произведения операторов равна произведению матриц сомножителей.

Следовательно, под оператором можно понимать квадратную матрицу размерности

12 3 4 5 6 Следующая ⇒