1. Численные методы, сложность и точность
1.1 Сложность алгоритма
Применение математических методов к решению инженерных задач обычно можно разбить на три этапа:
- Построение математической модели объекта или явления (математическая формулировка задачи). Модель должна правильно (адекватно) описывать рассматриваемое явление.
- Аналитическое исследование модели. В простых случаях удается найти точное решение построенной математической модели в виде формул, тогда процесс поиска решения задачи завершен. Но в большинстве случаев найти точное решение не удается. Это происходит главным образом потому, что искомое решение не выражается в привычных для нас элементарных или других известных функциях. Тогда переходят к следующему этапу.
- Выбор численного метода и численное решение задачи. Под численными методами подразумеваются методы решения задач, сводящиеся к арифметическим действиям над числами. Решение, полученное численным методом, представляет собой некоторые числовые значения, которые обычно являются приближенными, т.е. содержат некоторую погрешность. Часто после численного решения задачи приходится возвращаться к первому или второму этапу для коррекции математической модели и дополнительного исследования.
В курсе “Вычислительная математика” будут рассмотрены методы решения технических задач, представленных математической моделью.
При решении задачи численным методом возникают два важных вопроса:
- Выбор метода решения и разработка алгоритма допустимой трудоемкости.
- Достижение необходимой точности решения.
Эти вопросы тесно связаны друг с другом, и при их решении необходимо учитывать возможности используемой ЭВМ (быстродействие, объем оперативной памяти, наличие библиотеки стандартных подпрограмм и т.п.).
Рассмотрим две простые вычислительные задачи, встречающиеся (как подзадачи) при инженерных расчетах. На примере решения этих задач продемонстрируем зависимость сложности решения от выбранного алгоритма.
Первая задача – вычисление xn при большом n. Пусть, например, требуется вычислить x8. “Простой” способ (((((((x×
x)×
x)×
x)×
x)×
x)×
x)×
x) требует семь умножений. Другой способ ((x×
x)2)2 требует только трех умножений (три раза возводим в квадрат). В общем случае для вычисления xn можно рассмотреть такой способ: последовательно вычисляем x2, x4, ¼
, где t = [log2n] (округляем до ближайшего целого слева). Далее, рассмотрим представление числа n в двоичной системе счисления:n = (a
ta
t-1¼
a
1a
0)2.
Тогда, n = a
0 + 2a
1 + 22a
2 + ¼
+ 2ta
t в десятичной системе. Вычислим xn по схеме: xn = . Заметим, что если
a
i =0, то и умножение на эту единицу не производится. При таком подходе требуется t + w –1 умножение, где w – число ненулевых чисел среди a
1, a
2, ¼
, a
t. В худшем случае будет не более 2×
[log2n]–1 умножений. Но имеется и способ с меньшим числом умножений. Например, для вычисления x23 можно следующие промежуточные степени: x2, x4, x5, x10, x11, x22, x23. Такое вычисление требует 7 умножений.
Другая распространенная задача – вычисление значения многочлена n-ой степени для заданного значения x. “Простой” метод заключается в следующем: вычислим , затем и, окончательно, . При таком подходе будет выполнено (2n-1) умножений и n сложений. Другой способ вычисления значения многочлена известен под названием схема Горнера и использует следующее представление многочлена: . Таким образом, по схеме Горнера последовательно вычисляем выражения вида . В результате n умножений и n сложений получим . Доказано, что для многочленов общего вида нельзя построить схему с меньшим числом операций, чем схема Горнера. Такая схема удобна для реализации на ЭВМ, благодаря цикличности вычислений и необходимости хранить в памяти только коэффициенты многочлена и значения только одной промежуточной переменной Ai при текущем значении i. Таким образом, хорошо продуманная организация вычислений может существенно уменьшить время решения.
Попробуйте найдите способ вычисления x23 за 6 умножений.
1.2. Классификация погрешностей в численном анализе
Решение, полученное численным методом, является приближенным. Можно выделить три вида погрешностей.
1. Неустранимая погрешность. Эта погрешность может присутствовать даже, если решение поставленной математической задачи найдено точно. Сюда относится погрешность математической модели, т.к. никакая модель не может абсолютно точно описать изучаемое явление. Уменьшить эту погрешность можно только за счет усложнения модели. Выбрав определенную модель, мы неизбежно сталкиваемся с тем, что различные параметры, входящие в уравнения модели, а так же начальные данные заданы с некоторой погрешностью, так как они определяются в результате экспериментов и измерений. Уменьшить эту погрешность можно лишь за счет более точного определения параметров задачи.
2. Погрешность метода. Численные методы сами по себе являются приближенными, т.е. даже при отсутствии погрешностей во входных данных и при точном выполнении арифметических действий они дают решение задачи с некоторой погрешностью. Это происходит потому, что численным методом решается некоторая другая, более простая задача, приближенная к исходной. В ряде случаев численный метод строится на базе бесконечного процесса, который в пределе приводит к искомому решению. Однако, реально предельный переход не удается осуществить, и процесс, прерванный на некотором шаге, дает приближенное решение. Погрешность метода оценивается заранее через некоторые параметры метода. Такая погрешность может быть уменьшена путем изменения некоторого параметра метода.
3. Вычислительная погрешность. Возникает из-за округлений при выполнении арифметических операций над числами, приводящих к увеличению количества разрядов.
Полная погрешность решения, т.е. разность между полученным и точным решением задачи, не превосходит суммарного значения трех вышеназванных погрешностей.
1.3. Представление действительных чисел в ЭВМ
Как известно множество целых чисел бесконечно. Однако ЭВМ из-за ограниченной разрядной сетки может оперировать лишь с некоторым конечным подмножеством этого множества.
Для представления действительных чисел в современных ЭВМ используется форма с плавающей точкой. Десятичное число в этой форме записи имеет вид D = ±
M×
10p, где M – число с фиксированной точкой, называемое мантиссой числа (10-1 ≤
M <1), p- целое число, называемое порядком числа. Например, число 467.67 можно записать в виде 0.46767×
103. Из этой записи следует, что подмножество действительных чисел, с которыми оперирует конкретная ЭВМ, не является бесконечным. Оно конечно и определяется разрядностью k и границами порядка n1, n2 (n1 ≤
n ≤
n2). Можно показать, что это подмножество содержит 18×
( n2 – n1 + 1)×
a
k-1 + 1 чисел. Границы порядка n1, n2 определяют ограниченность действительных чисел по величине, а размерность k – дискретность распределения их на отрезке числовой оси. Например, в случае пятиразрядного машинного представления все значения, находящиеся в интервале между числами 0.35467 и 0.35468, представляются числом 0.35467 (при отбрасывании остальных разрядов без округления). Два соседних числа отличаются на единицу последнего разряда. Числа, меньшие единицы последнего разряда, воспринимаются как машинный нуль. Таким образом, ЭВМ оперирует с приближенными значениями действительных чисел, и необходимо уметь оценивать возникающую погрешность округления, а так же отслеживать ее изменение в процессе счета.
|