Полиномиальное раскачивание, он же феномен Рунге - особенно сильно проявляется на регулярных сетках (ага как раз в при интерполяции полиномом Ньтона), и с ростом степени полинома. чтоб избежать -сетка должна сгущаться к краям интервала (как в полиномах Чебышева). Но, наскольок я помню, проблемы с раскачкой ка таковой нет, поскольку в практике эти полиномы применялись для вычисления промежуточных значений табулированных функций (это когда калькуляторов не было, да и поездов наверное тоже). И для таких таблиц формировались разности для каждого фактически интевавала причем ка левые так и правые (т.е.е при увеличении Х и при уменьшении), соответсвенно при вычислении нужного значения брался средний интевал, на который влияли несколько соседних точек, но интерполированное значение вычислдялось для заданого интервала, а на сосодених интервалах, строились свои полиномы - на самом деле просто разности нескольких порядков. И еще достоинство метода - можно увеличить число точек к уже готовому полиному без проблем, нужно решить только одно дополнительное уравнение (для нерегулярных сеток) или добавить разность (но тут тольк олевую или правую). И еще - при анализе данных, можно по разностям понять, каким полиномом лучше описать данные - потому как разности ведут себя почти ка производные, так для линейной зависимости, вторые разности почти равны нулю, и.т.д.
А если узлы неравноотстоящие, мы же должны использовать разделенные разности для полинома в форме Ньютона. А у вас x-x0 и тд. Может быть у вас просто какая то другая форма или я что то не так понимаю?
Я показал два подхода. Для неравноотстоящих узлов - прямой метод вычисления коэффициентов через систему линейных уравнений (подстановкой координат точек). Для равноотстоящих узлов - с использованием конечных разностей.
@@learningmeansdoing Для неравноотстоящих узлов можно воспользоваться не конечными разностями, а разделёнными. Разделённая разность - это конечная, делённая на разность "иксов", соответствующим значениям функции в числителе. Разделённые разности тоже могут быть разной степени, только там надо очень внимательно следить за тем, какие иксы из чего вычитаются
Я надеюсь, я верно понял вопрос. Координата х3 используется в сплайне S2. Во-первых, сплайн S2 проходит через крайнюю правую точку с координатой x3. Во-вторых, мы задаем нулевую кривизну этого же сплайна в той же точке x3.
Скажите, а как определить момент перехода одной функции к другой? Например, несколько точек была линейная зависимость, а потом началась полиномиальная функция, как более точно определить этот перелом? Заранее спасибо!
Я бы сделал так. Берем три точки, стоящие рядом. Строим через 2 крайние из них отрезок прямой. Находим отклонение средней точки от построенной прямой. Когда это отклонение превысит допустимую величину, делаем вывод, что зависимость уже стала нелинейной. Это как вариант.
Чем чувствительнее будет ваш алгоритм обнаружения нелинейности, тем с одной стороны вы сможете точнее ее обнаружить, но с другой стороны растет риск ложных срабатываний. Так что это палка о двух концах.
Единственное нормальное видео. В других местах то степень потеряют в шаге, то разность криво вычислят, либо так рассказывают, что как будто специально, чтобы никто не понял ничего.
«Через 3 точки можно единственным образом провести кривую 2-го порядка» А можете пожалуйста обосновать почему это так. Что-то я не смог нагуглить. А в голове такие рассуждения:
Для тех, кто задался таким же вопросом. Ответ я нашёл. Пусть есть n+1 (x0, x1… xn) точка и два полинома P и Q степени n, которые в этих точках принимают одинаковое значение. Тогда рассмотрим L = P - Q. В точках x0, x1 … xn. В этих точках L = 0, значит это корни этого полинома. Значит у полинома L - n+1 корень. Однако у многочлена n степени, всего n корней. Получаем противоречие. На самом деле интуитивно это кажется не так)) Сколько кривых 2-го порядка можно провести через 2 точки? Бесконечно много. Получается, что все эти кривые больше нигде не пересекаются. Вот этот факт у меня вызвал сомнения.
Рассуждения лучше начинать так. Есть одна точка, через нее можно провести бесконечное количество прямых. Если же мы берем 2 точки (с разными координатами), то прямая, проходящая через эти точки, уже единственная. Дальше можно логику продолжать. Берем 2 точки и кривую второго порядка (параболу). Через 2 точки можно провести бесконечное множество кривых 2-го порядка. Но вот если мы берем 3 точки, то парабола уже единственная. У трех точек при этом должны быть разные координаты х. Ну и так далее...
Единственное видео, которое помогло понять интерполяцию методом Ньютона) Спасибо большое!
Спасибо огромное
Как раз сейчас использую в работе по цифровой обработке сигналов в реальном устройстве на микроконтроллере
Рад помочь
Полиномиальное раскачивание, он же феномен Рунге - особенно сильно проявляется на регулярных сетках (ага как раз в при интерполяции полиномом Ньтона), и с ростом степени полинома. чтоб избежать -сетка должна сгущаться к краям интервала (как в полиномах Чебышева).
Но, наскольок я помню, проблемы с раскачкой ка таковой нет, поскольку в практике эти полиномы применялись для вычисления промежуточных значений табулированных функций (это когда калькуляторов не было, да и поездов наверное тоже). И для таких таблиц формировались разности для каждого фактически интевавала причем ка левые так и правые (т.е.е при увеличении Х и при уменьшении), соответсвенно при вычислении нужного значения брался средний интевал, на который влияли несколько соседних точек, но интерполированное значение вычислдялось для заданого интервала, а на сосодених интервалах, строились свои полиномы - на самом деле просто разности нескольких порядков.
И еще достоинство метода - можно увеличить число точек к уже готовому полиному без проблем, нужно решить только одно дополнительное уравнение (для нерегулярных сеток) или добавить разность (но тут тольк олевую или правую).
И еще - при анализе данных, можно по разностям понять, каким полиномом лучше описать данные - потому как разности ведут себя почти ка производные, так для линейной зависимости, вторые разности почти равны нулю, и.т.д.
Большое спасибо, прекрасное видео!
Спасибо за хороший отзыв!
А если у меня много равноотстоящих узлов (21) , но нужно составить многочлен Ньютона 3-ей степени, как поступить?
Это уже не интерполяция, а приближение (регрессия). Подобрать многочлен 3 степени можно, но он не будет проходить через все точки.
А если узлы неравноотстоящие, мы же должны использовать разделенные разности для полинома в форме Ньютона. А у вас x-x0 и тд. Может быть у вас просто какая то другая форма или я что то не так понимаю?
Я показал два подхода. Для неравноотстоящих узлов - прямой метод вычисления коэффициентов через систему линейных уравнений (подстановкой координат точек). Для равноотстоящих узлов - с использованием конечных разностей.
@@learningmeansdoing Для неравноотстоящих узлов можно воспользоваться не конечными разностями, а разделёнными. Разделённая разность - это конечная, делённая на разность "иксов", соответствующим значениям функции в числителе. Разделённые разности тоже могут быть разной степени, только там надо очень внимательно следить за тем, какие иксы из чего вычитаются
Не понятно, а x3 почему не использовали, если дано?
Я надеюсь, я верно понял вопрос. Координата х3 используется в сплайне S2. Во-первых, сплайн S2 проходит через крайнюю правую точку с координатой x3. Во-вторых, мы задаем нулевую кривизну этого же сплайна в той же точке x3.
А если к координатам точек заданы еще и значения производных в этих точках, то только метод Эрмита годится или Ньютон тоже может их учесть?
Метод Ньютона не работает с производными. Вы все верно написали, что подойдёт метод Эрмита. У меня кстати есть видео об этом методе.
Скажите, а как определить момент перехода одной функции к другой? Например, несколько точек была линейная зависимость, а потом началась полиномиальная функция, как более точно определить этот перелом? Заранее спасибо!
Я бы сделал так. Берем три точки, стоящие рядом. Строим через 2 крайние из них отрезок прямой. Находим отклонение средней точки от построенной прямой. Когда это отклонение превысит допустимую величину, делаем вывод, что зависимость уже стала нелинейной. Это как вариант.
@@learningmeansdoing да это и я знаю...
Вроде неплохой вариант, и в реализации несложный
@@learningmeansdoing мне нужно сделать как можно точнее на ранних этапах, когда идёт отклонение от функции. Чем раньше тем лучше.
Чем чувствительнее будет ваш алгоритм обнаружения нелинейности, тем с одной стороны вы сможете точнее ее обнаружить, но с другой стороны растет риск ложных срабатываний. Так что это палка о двух концах.
Единственное нормальное видео. В других местах то степень потеряют в шаге, то разность криво вычислят, либо так рассказывают, что как будто специально, чтобы никто не понял ничего.
Благодарю за оценку моей работы!
А как делаеться эрмитовая интерполяция? А то все никак не могу найти настолько же доступно как у вас
На данный момент у меня такого видео нет, но в планах есть.
По просьбам трудящихся ua-cam.com/video/Czy6WgQVx8Q/v-deo.html
«Через 3 точки можно единственным образом провести кривую 2-го порядка»
А можете пожалуйста обосновать почему это так. Что-то я не смог нагуглить.
А в голове такие рассуждения:
Для тех, кто задался таким же вопросом. Ответ я нашёл.
Пусть есть n+1 (x0, x1… xn) точка и два полинома P и Q степени n, которые в этих точках принимают одинаковое значение.
Тогда рассмотрим L = P - Q. В точках x0, x1 … xn. В этих точках L = 0, значит это корни этого полинома. Значит у полинома L - n+1 корень. Однако у многочлена n степени, всего n корней. Получаем противоречие.
На самом деле интуитивно это кажется не так))
Сколько кривых 2-го порядка можно провести через 2 точки? Бесконечно много. Получается, что все эти кривые больше нигде не пересекаются. Вот этот факт у меня вызвал сомнения.
Рассуждения лучше начинать так. Есть одна точка, через нее можно провести бесконечное количество прямых. Если же мы берем 2 точки (с разными координатами), то прямая, проходящая через эти точки, уже единственная. Дальше можно логику продолжать. Берем 2 точки и кривую второго порядка (параболу). Через 2 точки можно провести бесконечное множество кривых 2-го порядка. Но вот если мы берем 3 точки, то парабола уже единственная. У трех точек при этом должны быть разные координаты х. Ну и так далее...