Корректность вычислительной задачи

Основные этапы решения прикладных задач с использованием компьютеров

1. Постановка проблемы — формулировка на языке предметной области.

2. Выбор, построение математической модели — полнота, сложность, снижение размерности — формулировка на математическом языке; упрощенная модель (грубая), тестовые примеры.

3. Постановка вычислительной задачи — анализ ИД, параметры модели, требования к результату, подготовка контрольных вариантов.

4. Анализ вычислительной задачи (существование и единственность решения, корректность, устойчивость).

5. Выбор численного метода — время решения, требуемая точность, универсальность.

6. Алгоритмизация — порядок вычислений, критерии окончания, контрольные точки и промежуточные проверки.

7. Обработка, представление и анализ результатов.

8. Корректировка модели, ИД, и т.п., возвращаемся к 1.

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

Пример. Найти решение уравнения ax + b = 0. Здесь исходные данные (ИД) — коэффициенты уравнения a и b, т.е. X = R² = {(a, b), a, b — действительные числа, a ≠ 0}, Y = R¹ = R — множество действительных чисел; задача имеет единственное решение . Если (a, b) = (3, 1), то решаем уравнение 3x+1 = 0.

Его единственное решение — .  

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

В дальнейшем будем обозначать (если специально не оговорено другое) y — точное, “теоретическое» решение задачи, x — точные, «теоретические» исходные данные; соответственно  y* и x* — их приближенные значения, еще y*— результат численного решения задачи.

Источники и классификация погрешностей численного решения задачи

 — погрешность численного решения задачи y = y(x).

Причины возникновения погрешностей:

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

 — неустранимая погрешность — погрешность модели, погрешность ИД;

 —погрешность метода — погрешность избранного численного метода; не следует стремиться сделать ее как можно меньшей, желательно — в 2-3 раза меньше неустранимой погрешности;

 — вычислительная погрешность — погрешность приближенных чисел, погрешность округления; следует стремиться сделать ее хотя бы на порядок меньше погрешности метода;

.

Корректность вычислительной задачи

Обозначим x* и y* — приближенные значения исходных данных и приближенное решение вычислительной задачи. Пусть определены их абсолютные и относительные погрешности, а также границы этих погрешностей

(эти понятия интуитивно ясны и известны, использовались в ЛП по физике, точные определения будут даны ниже).

Вычислительная задача называется корректной по Адамару - Петровскому, если:

1) при любых  существует решение ;

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

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

для любого  существует число ,  зависит от , такое, что всякому x*, удовлетворяющему условию , отвечает приближенное решение y*, для которого .

Задача некорректна, если нарушено хотя бы одно из этих условий.

Иногда рассматривают относительную устойчивость, т.е. в соответствующих неравенствах  и  заменяют соответственно на .