Прямая интерполяционная формула Ньютона

или первая интерполяционная формула Ньютона, применяется для интерполирования вперёд:   где  , а выражения вида   — конечные разности.

Функция f есть частный случай формулы Ньютона:

Выразим через x (h = 1):

где a = y_0, b = Δy_1, c = Δ²y_2.

Коэффициенты a, b, c для нашей квадратичной функции f находятся в первых ячейках строк экспериментальной таблицы 4.

Таблица 4. Коэффициенты производящей функции

Разрезы	0	1	2	3	4	…
Куски	y0 =1	2	4	7	11	…
Первые разности	–	Δy1 = 1	2 = 4 – 2	3 = 7 – 4	4 = 11 – 7	…
Вторые разности	–		Δ2y2 = 1	1 = 3 – 2	1 = 4 – 3	…

Итак, закономерность есть, и она такова:

f = a + b · x + c · x · (x – 1)/2 = 1 + x + x · (x – 1)/2 = 0.5 · x² + 0.5 · x + 1.

Теперь, когда закономерность определена, можно решить обратную задачу и ответить на поставленный вопрос: сколько надо выполнить разрезов, чтобы получить 821 кусок? x = ?

Решаем квадратное уравнение 821 = 0.5 · x² + 0.5 · x + 1, находим корни: x = 41.

Упражнение. Написать программу решения квадратного уравнения. Ответить на вопрос, для каких y имеет решение уравнение y = 0.5 · x² + 0.5 · x + 1?

Подведём итоги (обратите на это внимание!).

Сразу угадать решение мы не смогли. Поставить эксперимент оказалось затруднительно. Пришлось построить модель, то есть найти закономерность между переменными. Модель получилась в виде уравнения. Добавив к модели вопрос и уравнение, отражающее известное условие, образовали задачу. Поскольку задача оказалась типового вида (канонического), то её удалось решить известным методом.

Математический подход

Другой подход к решению задачи о разрезании пиццы дает дискретная математика.

Задача о разрезании пиццы

Формулировка задачи: сколько кусков пиццы можно получить, делая n прямолинейных разрезов ножом? Или, каково максимальное число L_n областей, на которые плоскость делится n прямыми?

Снова начнем с рассмотрения крайних случаев.

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

Т аким образом, L₃=4+3=7 – самое большое, что можно сделать.

Обобщая, приходим к следующему выводу: новая n-я прямая (при n>0) увеличивает число областей на k, когда рассекает k старых областей, то есть когда пересекает прежние прямые в (k−1) различных местах. Две прямые могут пересекаться не более чем в одной точке. Поэтому новая прямая может пересекать (n−1) старых прямых не более чем в (n−1) различных точках, и мы должны иметь k ≤ n. Установлена верхняя граница:

                                      L_n ≤ L_n-1+ n        при n>0 В этой формуле можно достичь равенства следующим образом: проводим n-ю прямую так, чтобы она не была параллельна никакой другой прямой (следовательно, она пересекает каждую из них) и так, чтобы она не проходила ни через одну из имеющихся точек пересечения (следовательно, она пересекает каждую из прямых в различных местах). Поэтому рекуррентное соотношение имеет вид:

L₀ = 1

L_n = L_n-1+ n             при n > 0

Теперь получим решение в замкнутой форме.

L_n = L_n-1+ n = L_n-2+ (n−1) + n = L_n-3+ (n−2) + (n−1) + n = … = L₀+1+2+…+(n−2)+(n−1) + n = 1 +  

L_n =  + 1     при n ≥ 0

Доказательство методом математической индукции приводится в книге Конкретная математика. Основание информатики.  Р. Грэхем, Д. Кнут, О. Паташник Пер. с англ. — М.: Мир, 1998. —703 с.