Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Устойчивость метода Гаусса.
Опуская обременительные преобразования в методе обратного анализа ошибок округления, отметим, что возмущенная система метода Гаусса имеет вид . Запишем оценку нормы матрицы возмущения: . Вид этой оценки удовлетворял бы критерию устойчивости Уилкинсона, если бы множитель g (A) имел небольшое значение. Поясним смысл множителя g( A ). Пусть обозначает матрицу, полученную из A после k шагов исключения. Обозначим . Тогда . Следовательно, g (A) показывает, во сколько раз могут возрасти элементы матрицы A в ходе исключения переменных по сравнению с их исходным уровнем. По этой причине g (A) называют коэффициентом роста матрицы A. Элементы активной части матрицы A k в методе Гаусса вычисляются по формуле . Для ограничения роста элементов матрицы в процессе гауссова исключения желательно, чтобы поправочные члены в этой формуле были не слишком большими. Это достигается процедурой выбора элемента , который называют главным. Выбор главного элемента по столбцу. В этом случае ограничение роста элементов матрицы A k на k –м шаге гауссова исключения достигается перестановкой строк таким образом, чтобы гарантировать неравенство . С этой целью при исключении переменной в качестве главного элемента выбирается элемент матрицы A k-1 по правилу , т. е. наибольший по модулю элемент в k –м столбце матрицы A k-1 (рис. 3.1). Строки r и k переставляются и только после этого выполняется k –й шаг исключения прямого хода Гаусса. При столбцовой стратегии выбора главных элементов справедлива такая оценка для значения параметра a k, определяющего коэффициент роста: . Она допускает, что и, следовательно, коэффициент роста . По этой причине метод Гаусса с выбором главного элемента по столбцам является условно устойчивым. Несмотря на это, он широко используется на практике, так как g (A) редко достигает своего верхнего предела. Выбор главного элемента по всей матрице. В этой стратегии в качестве главного элемента при исключении неизвестной x k выбирается элемент по правилу , т. е. наибольший по модулю элемент в квадратной подматрице матрицы A k-1 (рис. 3.2). Строки k и r, а также столбцы k и l переставляются и далее выполняется k –й шаг исключения. Такая стратегия гарантирует выполнение неравенства и, следовательно, ограничивает рост элементов в процессе исключения Гаусса. Оценка коэффициента роста элементов матрицы A в этом случае имеет более благоприятный вид: .
? 5. СЛАУ. Точность метода Гаусса. Направления повышенной точности. Точность метода Гаусса. Привлекая оценку нормы матрицы возмущения, можно записать, что . Анализ неравенства позволяет определить пути повышения точности метода Гаусса: выбор главных элементов, работа с числами удвоенной длины, переобусловливание системы линейных алгебраических уравнений. 6. Уравнение f(x)=0. Лемма об оценке погрешности приближенного решения. Пусть требуется решить уравнение , т. е. найти все корни , удовлетворяющие этому уравнению на отрезке . Задача численного решения уравнения сводится, во-первых, к отделению корней, во-вторых, к последующему уточнению корней. Лемма об оценке погрешности приближенного решения уравнения . Лемма. Пусть уравнение на отрезке имеет корень . Пусть найдено некоторое его приближенное значение . Тогда , где . Доказательство. Вычислим по теореме о конечных приращениях: . Очевидно, что . Отсюда , или . Лемма доказана. Величину называют невязкой. Из леммы следует, что судить о величине погрешности приближенного решения только по величине невязки нельзя. Необходимо учитывать и значение первой производной. Обратимся к рис. 7.2. Из этого рисунка следует, что одна и та же невязка приводит к существенно разным погрешностям приближенного решения, если производная в окрестности решения сильно отличается.
7. Уравнение f(x)=0. Метод итераций. Теорема о сходимости и точности. Пусть требуется решить уравнение , т. е. найти все корни , удовлетворяющие этому уравнению на отрезке . Задача численного решения уравнения сводится, во-первых, к отделению корней, во-вторых, к последующему уточнению корней. Метод итераций. Для построения метода итераций преобразуем уравнение к виду . Это можно сделать в общем случае так: , или , где . Постоянный множитель h выбирается при этом из условия сходимости метода (установим его позже). Пусть известно начальное приближение . Тогда Приведенный способ построения числовой последовательности реализуется в методе итераций: . Рассмотрим, как ведет себя погрешность решения на итерациях метода. Обозначим , где - погрешности приближенного решения на двух соседних итерациях. Подставим представленные таким образом и в итерационное правило: . Разложим функцию в ряд Тейлора в окрестности точки : . Пренебрегая остаточным членом , получим соотношение, связывающее погрешность решения метода на двух соседних итерациях: . Сделаем некоторые выводы на основании этого приближенного равенства. · Если , то можно ожидать, что и последовательность будет сходиться к решению, когда начальное приближение выбрано достаточно близким к . · Если , то скорее всего и метод будет расходиться, так как каждое последующее приближение будет отстоять от решения дальше, чем предыдущее. · При и погрешности и имеют одинаковые знаки. Сходимость будет монотонной. · При и погрешности и имеют разные знаки. Сходимость является немонотонной. Проиллюстрируем характер сходимости метода итераций графически. Образуем функции . В решении задачи значения этих функций совпадают. Первый пример (см. рис. 7.3, а) соответствует условиям и, следовательно, в этом случае наблюдается монотонная сходимость метода итераций. В следующем примере (см. рис. 7.3, б) , поэтому имеет место немонотонная сходимость. В последнем примере (см. рис. 7.3, в) . При таких значениях производной метод итераций расходится.
Рис. 7.3. Иллюстрация сходимости метода итераций
|