Что именно доказывает-то? Что многочлен степени n однозначно задается n+1 точками, и наоборот, любой набор n+1 точек кривой многочлена однозначно его задает?
мм... корни как корни... тут вообще надо в сторону интерполяции смотреть полиномы например так выглядят: y=y3*(x-x1)*(x-x2)/[(x3-x1)*(x3-x2)]+y1*(x-x2)*(x-x3)/[(x1-x2)*(x1-x3)]+y2*(x-x1)*(x-x3)/[(x2-x1)*(x2-x3)]
Имхо тут Кнут может и ошибаться.... Помню в универе говорили, что степенной многочлен (Тейлора, Маклорена) построенный по n точкам вовсе не обязан их "плавно соединять", а вполне может в промежутках и "фортеля выписывать"... Тогда я тоже в это не особо поверил, а потом на практике столкнулся - дойдут рки восстановлю программку из которой это видно.
Вроде Кнут всё и объяснил... Подробнее: 1. Мы доказываем некоторое тождество (формулу на скриншоте). 2. Рассматриваем левую и правую части тождества как функции от r. 3. По определению биномиальных коэффициентов левая и правая части - многочлены от r. 4. Ранее было доказано, что для бесконечно многих значений r левая и правая части совпадают. 5. Рассмотрим разность левой части и правой части. Это также будет многочлен от r, назовём его P. 6. Мы хотим доказать, что P нулевой. Это и будет означать, что тождество выполнено всегда (для всех r). 7. Рассуждаем от противного. Пусть P ненулевой. Обозначим его степень через n. 8. Поскольку для бесконечно многих значений r левая и правая части совпадают, то можно найти n+1 значение r, для которого обе части равны и, следовательно, P обращается в нуль. 9. Таким образом, у P не менее n+1 корней. 10. По формуле Безу если P(a)=0, то P делится на (x-a). 11. Следовательно, если P(a_1)=P(a_2)=...=P(a_{n+1})=0 и все a_i различны, то P делится на (x-a_1)...(x-a_{n+1}). 12. Но многочлен P имеет степень n и не может делиться на многочлен степени n+1. 13. Получили противоречие. Следовательно, P должен быть нулевым и формула верна для всех r. Может, причём запросто (классический пример - при приближении хорошей функции 1/(1+25x^2) по равномерной сетке на [-1,1] при увеличении числа точек получающиеся многочлены вне точек сетки и не думают приближаться к приближаемой функции, а неограниченно растут). Только речь идёт совсем не о том.
AssemblerIA64 Кнут доказывает не формулу на скриншоте, а формулу (8). Формула на скриншоте - вспомогательный инструмент, эквивалентный (8) при r\ne k. Формула (8) доказана в частном случае, когда r - положительное целое число, не равное k (иначе тождество (6), на которое опирается доказательство, теряет смысл). А рассуждение призвано доказать общий случай, когда r - произвольное число (не обязательно целое положительное), не равное k. Причём рассуждение опирается на то, что для частного случая всё уже доказано, и фактически обобщает.
Ещё мне непонятно, почему Кнут пишет (стр. 93): "Можно предположить, что r ≠ kt ≠ s для 0 ≤ k ≤ n, так как обе части (30) - это многочлены по r, s, t".
По той же самой причине, что и здесь. Сначала доказываем утверждение для бесконечно многих значений параметров (условие r\ne kt\ne s - не сильно ограничивающее, для каждой переменной при фиксированных остальных остаётся бесконечно много вариантов), потом говорим, что раз два многочлена равны при бесконечно многих значениях переменной, то они тождественно равны. В данном случае "потом говорим" опущено (подразумевается мысленно).
Возникла ещё одна проблема: я не понимаю переход к теореме B (2-ой том, 311-ая страница). Благодарю за любую помощь.
Правое неравенство, q <= \hat{q}, - это утверждение теоремы А выше на той же страницы. Логика доказательства левого неравенства следующая: Предположим, что \hat{q} >= q+3. Тогда <здесь выкладки, доказывающие, что в этом случае> v_{n-1} < \lceil b/2 \rceil. Следовательно, если v_{n-1} >= \lceil b/2 \rceil, то \hat{q} < q+3, то есть (в силу того, что q и \hat{q} натуральные) \hat{q} <= q+2.
diamond, спасибо. Только у меня остался вопрос: почему \hat{q} <= q+2? В числовых примерах это неравенство просматривается хорошо, только непонятно, как это строго показать.
Эээ... ну так Кнут это и доказывает, только перед формулировкой теоремы B - все выкладки между концом доказательства теоремы A и формулировкой теоремы B как раз и образуют доказательство (от противного).
diamond, да, что-то намудрил я вчера. Мне было непонятно, почему во второй части неравенства стоит 2. Теперь разобрался. Спасибо Вам ещё раз!
