Обусловленность задачи и метода. Сложность вычислительной задачи.

 

В практических и научных вычислениях могут происходить следующие ошибки следующих видов:

1.     Неправильная работа машинных устройств (сбои машин - редкие ошибки).

2.     Ошибки программиста (неправильно составлена программа).

3.     Ошибки эксперимента (неточность измерений).

4.     Игнорирование существенных особенностей задачи.

5.     Ошибка вычислений или ошибка округления зависит от двух факторов:

-         обусловленности или чувствительности задачи;

-         устойчивости алгоритма.

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

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

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

 

2. Примеры неустойчивых задач.

1)     Линейная система

имеет единственное решение x =1, y = 1. Увеличим свободный член первого уравнения в 0,01  и получим возмущенную систему

.

Полученная система имеет решение x =11,01, y = 0. Оно сильно отличается от решения первой системы.

2)     Уравнение

имеет два действительны и два комплексных корня: x1=2,01, x2=1,99, x3=2+0,01i, x4=2-0,01i.

Если мы работаем на компьютере, для которого eмаш>10-10, то компьютер, независимо от метода, которым решается уравнение

,

найдет только один действительный корень: x1=2. Эта задача плохо обусловлена.

3)     Рассмотрим ряд  . Тогда для x = -15 получим следующие результаты: n = 20, e-15 » 136678,6; n = 21, e-15 » -97627б,55; n = 51, e-15 » -6,166608*10 -7 ; n = 52,   e-15 »1,778677*10 -7. Если при будем вычислять по формуле

,

то получим сходимость e-15 » 3,059023*10-7.  Таким образом, первый метод вычисления неустойчив, а второй устойчив.

4)     При вычислении определенного интеграла  можно применить рекуррентную формулу In = 1 - nIn-1; n = 1,2,…; I0 = 1-1/e. При проведении вычислений I14 разброс значений составил от -147 до 5356. Здесь мы имеем неустойчивость метода.

 

3.     Сложность вычислительной задачи

 

Всякая задача при постановке на ЭВМ определяет совокупность алгоритмов для ее решения, которые дают различные приближенные решения задачи. Среди решений есть близкие к точному решению и очень далекие от него. Среди решений задачи трудно найти решение близкое к точному. Разброс приближенных решений говорит о степени неустойчивости задачи. Но о принципиальной возможности оптимизации алгоритмов забывать не следует. Даже простым изменением порядка суммирования можно уменьшить оценки ошибки в n/log 2 n раз.

Важно, чтобы алгоритм решения задачи был устойчив к конкретной ЭВМ.

При оценке погрешностей задачи и при описании сложности вычислительных алгоритмов используют символ Ландау O(p), "О большое от p", который имеет следующий смысл.

Определение 3.1. Пусть имеются две функции f(x) и g(x) >0, определенные при x ® x0. Говорят, что f(x)=O(g(x)), если существует такая постоянная A>0, что при всех x достаточно близких к x0 имеет место неравенство |f(x)| < Ag(x).

Таким образом, соотношение f(x) =O(g(x)) обозначает, что функция f(x) по модулю при        x ® x0 растет медленнее, чем функция g(x).

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

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

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

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

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