ОБ ОДНОМ ПОДХОДЕ РАЗРАБОТКИ АЛГОРИТМА С ПРИМЕНЕНИЕМ ДИНАМИЧЕСКОЙ ПАМЯТИ

АННОТАЦИЯ

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

ABSTRACT

One of the most important prerequisites for a successful solution of the presented problem is the implementation of efficient programming. To achieve this, it is important to use computer memory sparingly. This article discusses the possibility of using dynamic memory in solving the interpolation problem.

Ключевые слова: Интерполяционные формулы Ньютона, динамическая память, статическая память, эффективность алгоритма, объем информации, рекурсивные вычисления, информационные структуры.

Keywords: Newton's interpolation formulas, dynamic memory, static memory, algorithm efficiency, amount of information, recursive calculations, information structures.

Введение. Как правило, неопытные программисты при составлении алгоритмов воспользуются статической памятью, в то время как можно использовать динамическую память для решения конкретной задачи. Необходимость применения динамической памяти, например, возникает в то время, когда объем обрабатываемой информации заранее неизвестно, и выясняется только в ходе решения задачи [5].     В этом случае для гарантии удачного решения априорно можно зарезервировать статическую память с большим объемом. Однако при этом определенная часть выделенной памяти будет пассивно участвовать при решении задачи. Такая ситуация задерживает ход решения, поэтому подобный алгоритм будет неэффективным [1,3].

В данной статье рассматривается задача интерполяции статистических данных функциональной зависимости y=f(x), которая реализуется с применением динамической памяти [2].

Постановка задачи. Допустим, каждому значению аргумента x_i соответствует некоторое значение y_i  зависимой переменной y, где 0≤i≤n. Требуется определить значение y=f(x) для .

Согласно первой интерполяционной формуле Ньютона [4]:

   (1)

Здесь: ;

  и т.д.

Метод решения. Одним из важнейших моментов эффективности алгоритма для формулы (1) является разработка блока, вычисляющего выражения y₀ , для этого будем использовать информационную структуру:

1) S[1:2;1:k]- это двухмерный динамический массив, здесь к- количество столбцов:

2) a[1:k]- одномерный массив (вектор), который строится по данным массива S по формуле: =(a₁,...,a_k)=(S₂₁-S₁₁,S₂₂-S₁₂,…, S_2К-S_1К ); S_ij, a_jZ, ; 1≤ j≤ k; 2≤ k ≤n.

Начальное состояние массива S соответствует значению к=2:

при этом вектор строится по формуле:

=(S₂₁-S₁₁,S₂₂-S₁₂)=(-1;1)                      (2)

Используя эти обозначения показатель  можно представить в виде скалярного произведения вектора  , построенного по формуле (2) и вектора , при этом получим:

.

В следующих расчетах при к≥3 массивы S[1:2;1:k] и a[1:k] строятся рекурсивно, ссылаясь на информацию для к-1, об этом подробно излагается в алгоритме на рис.1. При к=3 получим следующие результаты:

 a=(S₂₁-S₁₁, S₂₂-S₁₂, S₂₃-S₁₃)=(1, -2, 1).

 Таким образом имеем:

Аналогично вычисляются  и т.д.

Как видно, предлагается алгоритм, который работает рекурсивно, при этом количество столбцов массивов S и a от шага к шагу наращиваем на единицу.

Данный подход можно реализовать при применении обратной интерполяционной формулы (3) Ньютона и оценить коэффициенты многочлена [2,4]:

   (3)

Рассмотрим ход работы массивов S и a в этом случае.

При к=2 получаем:

=(S₁₁-S₂₁,S₁₂-S₂₂)=(1,-1).

Следовательно, показатель можно вычислить как скалярное произведение векторов  и  :

При к=3 имеем 

a=(S₁₁-S₂₁, S₁₂-S₂₂, S₁₃-S₂₃)=(1, -2, 1)

, и т.д.

Рисунок 1. Алгоритм вычисления показателей для первой интерполяционной формулы Ньютона

Рисунок 2. Алгоритм вычисления функции f(x) по первой интерполяционной формуле Ньютона

Список литературы:

1. Ахо А., Хопкроп Д. Построение и анализ вычислительных алгоритмов. М.: Мир, 1980, 326 стр.
2. Бахвалов Н.С. Численные методы-М: “Наука”, 1975, 631 стр.;
3. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.- М.: Мир, 1982, 191 стр.;
4. Демидович Б.П., Марон И.А. Основы вычислителъной математики.-М: “Наука”,1970, 670 cтр.;
5. Donald E. Knuth.The Art of Computer Programming: Volume 1: Fundamental Algorithms. Third Edition xx+650pp. ISBN 0-201-89683-4, Reading, Massachusetts: Addison-Wesley, 1997, 666 рр.