Накопление Погрешности

При численном решении алгебраических уравнений — суммарное влияние округлений, сделанных на отдельных шагах вычислительного процесса, на точность полученного решения линейной алгебраич. системы. Наиболее распространенным способом априорной оценки суммарного влияния ошибок округления в численных методах линейной алгебры является схема т. н. обратного анализа. В применении к решению системы линейных алгебраич. уравнений схема обратного анализа заключается в следующем. Вычисленное прямым методом Мрешение хуи не удовлетворяет (1), но может быть представлено как точное решение возмущенной системы Качество прямого метода оценивается по наилучшей априорной оценке, к-рую можно дать для норм матрицы и вектора . Такие "наилучшие"и наз. соответственно матрицей и вектором эквивалентного возмущения для метода М. Если оценки для и имеются, то теоретически ошибка приближенного решения может быть оценена неравенством Здесь — число обусловленности матрицы А, а матричная норма в (3) предполагается подчиненной векторной норме В действительности оценка для редко бывает известна, и основной смысл (2) состоит в возможности сравнения качества различных методов. Ниже приводится вид нек-рых типичных оценок для матрицы Для методов с ортогональными преобразованиями и арифметики с плавающей запятой (в системе (1) Аи bсчитаются действительными) В этой оценке — относительная точность арифметич. операций в ЭВМ,- евклидова матричная норма, f(n) — функция вида , где п- порядок системы. Точные значения константы Си показателя kопределяются такими деталями вычислительного процесса, как способ округления, использование операции накопления скалярных произведений и т. д. Наиболее часто k=1 или 3/2. В случае методов типа Гаусса в правую часть оценки (4) входит еще множитель , отражающий возможность роста элементов матрицы Ана промежуточных шагах метода по сравнению с первоначальным уровнем (такой рост отсутствует в ортогональных методах). Чтобы уменьшить значение , применяют различные способы выбора ведущего элемента, препятствующие возрастанию элементов матрицы. Для квадратного корня метода, к-рый применяется обычно в случае положительно определенной матрицы А, получена наиболее сильная оценка Существуют прямые методы (Жордана, окаймления, сопряженных градиентов), для к-рых непосредственное применение схемы обратного анализа не приводит к эффективным оценкам. В этих случаях при исследовании Н. п. применяются и иные соображения (см. [6] — [9]). Лит.:[1] Givens W., "TJ. S. Atomic Energy Commiss. Repts. Ser. OR NL", 1954, № 1574; [2] Wilkinson J. H., Rounding errors in algebraic processes, L., 1963; [3] Уилкинсон Д ж. Для устойчивых методов характерен рост погрешности как Оценка погрешности таких методов обычно производится следующим образом. Строится уравнение относительно возмущения, вносимого или округлением, или погрешностями метода и затем исследуется решение этого уравнения (см. [2], [3]). В более сложных случаях применяется метод эквивалентных возмущений (см. [1], [4]), развитый в отношении задачи исследования накопления вычислительной погрешности при решении дифференциальных уравнений (см. [3], [5], [6]). Вычисления по нек-рой расчетной схеме с округлениями рассматриваются как вычисления без округлений, но для уравнения с возмущенными коэффициентами. Сравнивая решение исходного сеточного уравнения с решением уравнения с возмущенными коэффициентами получают оценку погрешности. Уделяется существенное внимание выбору метода по возможности с меньшими значениями qи A(h). При фиксированном методе решения задачи расчетные формулы обычно удается преобразовать к виду, где (см. [3], [5]). Это особенно существенно в случае обыкновенных дифференциальных уравнений, где число шагов в отдельных случаях оказывается очень большим. Величина (h)может сильно расти с ростом промежутка интегрирования. Поэтому стараются применять методы по возможности с меньшим значением A(h). В случае задачи Коши ошибка округления на каждом конкретном шаге по отношению к последующим шагам может рассматриваться как ошибка в начальном условии. Поэтому нижняя грань (h)зависит от характеристики расхождения близких решений дифференциального уравнения, определяемого уравнением в вариациях. В случае численного решения обыкновенного дифференциального уравнения уравнение в вариациях имеет вид и потому при решении задачи на отрезке ( х 0 , X )нельзя рассчитывать на константу A(h)в мажорантной оценке вычислительной погрешности существенно лучшую, чем Поэтому при решении этой задачи наиболее употребительны однощаговые методы типа Рунге — Кутта или методы типа Адамса (см. [3], [7]), где Н. п. в основном определяется решением уравнения в вариациях. Для ряда методов главный член погрешности метода накапливается по подобному закону, в то время как вычислительная погрешность накапливается существенно быстрее (см. [3]). Область практич. применимости таких методов оказывается существенно уже. Накопление вычислительной погрешности существенно зависит от метода, применяемого для решения сеточной задачи. Напр., при решении сеточных краевых задач, соответствующих обыкновенным дифференциальным уравнениям, методами стрельбы и прогонки Н. п. имеет характер A(h)h-q, где qодно и то же. Значения A(h)у этих методов могут отличаться настолько, что в определенной ситуации один из методов становится неприменимым. При решении методом пристрелки сеточной краевой задачи для уравнения Лапласа Н. п. имеет характер с 1/h, с>1, а в случае метода прогонки Ah-q. При вероятностном подходе к исследованию Н. п. в одних случаях априорно предполагают какой-то закон распределения погрешности (см. [2]), в других случаях вводят меру на пространстве рассматриваемых задач и, исходя из этой меры, получают закон распределения погрешностей округления (см. [8], [9]). При умеренной точности решения задачи мажорантные и вероятностные подходы к оценке накопления вычислительной погрешности обычно дают качественно одинаковые результаты: или в обоих случаях Н. п. происходит в допустимых пределах, или в обоих случаях Н. п. превосходит такие пределы. Лит.:[1] Воеводин В. В., Вычислительные основы линейной алгебры, М., 1977; [2] Шура-Бура М. Р., "Прикл. матем. и механ.", 1952, т. 16, № 5, с. 575-88; [3] Бахвалов Н. С, Численные методы, 2 изд., М., 1975; [4] Уилкинсон Дж. X., Алгебраическая проблема собственных значений, пер. с англ., М.. 1970; [5] Бахвалов Н. С, в кн.: Вычислительные методы и программирование, в. 1, М., 1962, с, 69-79; [6] Годунов С. К., Рябенький В. С, Разностные схемы, 2 изд., М., 1977; [7] Бахвалов Н. С, "Докл. АН СССР", 1955, т. 104, № 5, с. 683-86; [8] его же, "Ж. вычислит, матем. и матем. физики", 1964; т. 4, № 3, с. 399- 404; [9] Лапшин Е. А., там же, 1971, т. 11, № 6, с.1425-36. Н. С. Бахвалов.