С. Л. Гольдштейн А. В. Кибардин информатика для физиков часть Введение Учебное пособие

5.4 Вычислительный алгоритм. Введение в численные методы

Для реализации конкретной математической модели необходимо составить алгоритм ее решения на ЭВМ.

Алгоритмом называется конечная последовательность однозначно понимаемых элементарных действий (шагов), направленная на решение конкретной задачи.
Перечислим основные свойства алгоритма:

1. 
   дискретность – алгоритм должен состоять из отдельных, конечных во времени шагов;
   
2. 
   однозначность – каждый шаг алгоритма должен быть однозначно понимаем;
   
3. 
   конечность – алгоритм должен приводить к решению задачи за конечный промежуток времени;
   
4. 
   массовость – алгоритм должен формулироваться в общем виде, т.е. быть применимым к целому классу задач, отличающихся лишь исходными данными.
   

В компьютерном моделировании под методом (алгоритмом) будем понимать:

• 
  формулировку исходной математической модели в виде дискретной задачи;
  
• 
  собственно разработку вычислительного алгоритма для решения этой задачи на ЭВМ.
  

Что означает термин “дискретная задача”? Это значит, что исходная математическая модель должна быть сформулирована в виде, пригодном для решения на ЭВМ. Например: если исходная задача сформулирована в виде дифференциального уравнения или системы дифференциальных уравнений, то для численного решения на ЭВМ ее необходимо заменить системой линейных или разностных алгебраических уравнений. В этом случае говорят, что проведена дискретизация исходной математической задачи.
Формулировкой дискретных задач и составлением вычислительных задач занимается раздел прикладной математики, называемый “Численные методы”.

Базовые понятия численных методов

В численных методах функции непрерывного аргумента заменяются функциями целочисленного аргумента – сеточными функциями. Сеточную функцию можно рассматривать как функцию целочисленного аргумента.

y=y(x) y=y(x_i)=y(i)=y_i i=1,2..n

y y

х х₁ х_n

Рис. 5.2
Разностью первого порядка будем называть результат вычитания двух соседних значений y:
y_i=y_i+1-y_i (правая разность) (5.4)
y_i=y_i-y_i-1 (левая разность) (5.5)

Предположим, что надо вычислить сумму значений

y_n =x₁+ x₂+…+ x_n= . (5.6)

Тогда вычисления организуются следующим образом. Задается начальное значение y₀=0, а затем последовательно, начиная с i=1, находятся числа y_i, связанные реккурентным соотношением

y_i= y_i-1+x_i, i=1, 2, …n. (5.7)

Для вычисления произведения вида
y_n =x₁*x₂*…* x_n= (5.8)
достаточно задать начальное значение у₀=1 и воспользоваться реккурентным соотношением
y_i= y_i-1*x_i, i=1, 2, …n. (5.9)

Уравнения (5.7) и (5.9) являются частным случаем линейного разностного уравнения первого порядка:

у_i=q_i*y_i-1+f_i , i=1,2,…n, (5.10)
где q_i, f_i - заданные числа, а у_i – искомые значения.
Для данного уравнения рассматривается задача нахождения всех у_i при заданном значении у₀ . Ясно, что решение этой задачи существует и оно единственно.