Рекуррентное соотношение ортогональных многочленов

[ktoto]

В литературе всюду появляется рекуррентное соотношение для ортогональных многочленов:

${p_{n+1}(x)\ =\ (A_nx+B_n)\ p_n(x)\ -\ C_n\ p_{n-1}(x)}$

Каким образом приходят к данному выражению?

[ИСН]

В литературе всюду появляется такое соотношение для досок, что толщина их равна 2, а ширина - 4 дюйма. Каким образом к нему приходят?

[marij]

Похоже на рекуррентное соотношение для вычисления интегралов

[ewert]

ktoto в сообщении #919394 писал(а):

Каким образом приходят к данному выражению?

Коэффициент $A_n$ -- нормировочный, и его можно считать равным единице (т.е. строить последовательность многочленов с единичными старшими коэффициентами). Тогда $B_n,C_n$ определяются из этого соотношения однозначно условиями ортогональности $p_{n+1}(x)$ к $p_{n}(x)$ и к $p_{n-1}(x)$. Ко всем же предыдущим $p_{k}(x),\;k<n-1$ ортогональность тогда будет выполнена автоматически: $\big((x+B_n)p_n+C_np_{n-1}\big)\perp p_k\ \Leftrightarrow\ x\cdot p_n\perp p_k$, последнее же верно просто потому, что степень многочлена $x\cdot p_k$ меньше $n$.

[Red_Herring]

ИСН в сообщении #919409 писал(а):

В литературе всюду появляется такое соотношение для досок, что толщина их равна 2, а ширина - 4 дюйма. Каким образом к нему приходят?

Обман, кругом обман!. Т.н. 2 by 4 (он же 2"x4") на самом деле много лет как 11⁄2"×31⁄2" http://en.wikipedia.org/wiki/Lumber#Dimensional_lumber. Но в длину не врут (там 8' это 8' без усядок и утрусок!)

[ktoto]

ewert в сообщении #919415 писал(а):

ktoto в сообщении #919394 писал(а):

Каким образом приходят к данному выражению?

Коэффициент $A_n$ -- нормировочный, и его можно считать равным единице (т.е. строить последовательность многочленов с единичными старшими коэффициентами). Тогда $B_n,C_n$ определяются из этого соотношения однозначно условиями ортогональности $p_{n+1}(x)$ к $p_{n}(x)$ и к $p_{n-1}(x)$. Ко всем же предыдущим $p_{k}(x),\;k<n-1$ ортогональность тогда будет выполнена автоматически: $\big((x+B_n)p_n+C_np_{n-1}\big)\perp p_k\ \Leftrightarrow\ x\cdot p_n\perp p_k$, последнее же верно просто потому, что степень многочлена $x\cdot p_k$ меньше $n$.

Вы уже перешли к доказательству.

Действительно наверное вопрос который я задал, имеет мало смысла.
Реккурентная формула, по моему мнению, находиться через рассмотрения множеств ортогональных многочленов, (Лежандра, Эрмита, Чебышева и др.), а далее делается обобщение, до вида указаного в вопросе?

Спасибо всем откликнувшимся.

[ewert]

ktoto в сообщении #919565 писал(а):

Реккурентная формула, по моему мнению, находиться через рассмотрения множеств ортогональных многочленов, (Лежандра, Эрмита, Чебышева и др.), а далее делается обобщение, до вида указаного в вопросе?

Вообще-то наоборот -- это общее свойство любых ортогональных многочленов. Если говорить о математической стороне дела. Если же об исторической, то я не в курсе.

[ktoto]

ewert в сообщении #919817 писал(а):

ktoto в сообщении #919565 писал(а):

Реккурентная формула, по моему мнению, находиться через рассмотрения множеств ортогональных многочленов, (Лежандра, Эрмита, Чебышева и др.), а далее делается обобщение, до вида указаного в вопросе?

Вообще-то наоборот -- это общее свойство любых ортогональных многочленов. Если говорить о математической стороне дела. Если же об исторической, то я не в курсе.

То есть из общего решения дифференциального уравнения второго порядка, получаем частные решения, которого являются многочлены (Лежандра, Эрмита, Чебышева и др.)? И из этого общего решения же получаем, общее рекуррентное соотношение? Так?

По поводу общего вида рекуррентного соотношения:

Цитата:

Вообще-то наоборот -- это общее свойство любых ортогональных многочленов.

А если мы имеет ортогональные многочлены от линейно-независимой системы скажем такой $\{e^{kx}\}_{k=0}^m$, будет ли данное выше свойство рекуррентности справедливо для них, то есть насколько оно действительно общее?
Или в рекуррентном соотношении просто приходим к замене: $\{x^k\}_{k=0}^m \longmapsto \{e^{kx}\}_{k=0}^m$

${p_{n+1}(x)\ =\ (A_n e^x+B_n)\ p_n(x)\ -\ C_n\ p_{n-1}(x)}$

А в общем виде: для системы ортогональных многочленов $\{p_n(x)\}_{n=0}^m$, полученных из линейно-независимой системы: $\{\varphi_{k}(x)\}_{k=0}^m$,
будем иметь:

${p_{n+1}(x)\ =\ (A_n\varphi_1(x)+B_n)\ p_n(x)\ -\ C_n\ p_{n-1}(x)}$

Это верно?
Видимо тут нужно доказывать

[profrotter]

Видел похожий материал: http://library.mirea.ru/media/upfile/vestnik11.pdf стр.55

[ktoto]

profrotter в сообщении #919846 писал(а):

Видел похожий материал: http://library.mirea.ru/media/upfile/vestnik11.pdf стр.55

Да спасибо неплохая статья, но всё равно не понятно из логики откуда берётся рекуррентное соотношение(подчёркнуто красным), берётся как данность, потом доказывается:

Может быть это и есть Эврика ?

[ktoto]

По моему более простое объяснение для появления общего рекуррентного соотношения это ортогонализация Грама-Шмидта:
$ \\ \varphi_0 = e_0 \\ \varphi_1 = e_1 + \alpha_1 e_0 \\ \varphi_2 = e_2 + \alpha_2 e_0 + \beta_1 e_1 $

далее замена сохраняющая номер(или степень многочлена когда говорят о степенной функции) (1+1 = 2): $\varphi_2(x) = \varphi_1(x) e_1(x) $, правда такая агрессивная замена тоже требует некоторого доказательства, но если не углубляться, то на первое время сойдёт.

$ \\ e_0 = \varphi_0 \\ e_1 = \varphi_1 - \alpha_1 e_0 \\ e_2 = \varphi_1 e_1 - \alpha_2 e_0 - \beta_1 e_1 $

или: $e_2 = (\varphi_1 - \beta_1) e_1 - \alpha_2 e_0 $

далее как говорится по индукции:

$e_{n+1}(x) = (\varphi_1(x) - \beta_n) e_n(x) - \alpha_{n+1} e_{n-1}(x) $

.

[ktoto]

Едиственная проблема, что в случае более общей замены:

$\varphi_2(x) = (A \varphi_1(x) + B \varphi_0(x) + D) e_1(x) $

подставкой в:

$ e_2 = \varphi_2 - \alpha_2 e_0 - \beta_1 e_1 $

используя допущение:

$\varphi_0(x) e_n = e_n$

из двух уравнений:

$ \begin{cases} (e_2, e_0) = 0 \\ (e_2, e_1) = 0 \\ \end{cases} $

удаётся определить $e_2$ сточность до константы, $C$.
т.е.:

$ e_{n+1}(x) = C [(\varphi_1(x) - \beta_n) e_n(x) - \alpha_{n+1} e_{n-1}(x)] $

Что забыл?
Или как получить $ C $ ?

[profrotter]

А $C$ может быть произвольной - на ортогональность не повлияет. Выбирают её обычно так, чтобы норма у многочлена была единичной (я все выкладки не смотрел, только последнее равенство).

Если мне не изменяет память, рекуррентное соотношение вместе с процедурой Грама-Шмидта рассматривается в главе 10, п.п. 10.4-10.5 в Вержбицкий В. М. Основы численных методов : [учебник для студентов вузов, обучающихся по направлению подготовки дипломированных специалистов "Прикладная математика"] / В. М. Вержбицкий .— Изд. 2-е, перераб. — М. : Высшая школа, 2005.

[ktoto]

profrotter в сообщении #921130 писал(а):

Если мне не изменяет память, рекуррентное соотношение вместе с процедурой Грама-Шмидта рассматривается в главе 10, п.п Вержбицкий В. М. Основы численных методов

И да и нет, в книге используется процедура Г-М на ряду с использование рекуррентного соотношения:
-

То есть общая рекуррентная формула (3.29) просто берётся как данность, а также волшебным образом единице принимается коэффициент $\alpha_n$, а дальше уже показывается что построенные таким образом многочлены будут ортогональны.

На счёт нормировки:

$ \\ \varphi_0 = e_0 \\ \varphi_1 = e_1 + \alpha_1 e_0 \\ \varphi_2 = e_2 + \alpha_2 e_0 + \beta_1 e_1 \ \ \ \ (1) $

Выразим $e_2$ из (1):
$e_2 = \varphi_2 - \alpha_2 e_0 - \beta_1 e_1 \ \ \ \ (2)$

Cделаем предположение что $\varphi_2$ можно выразить через $\varphi_1$ и $e_1$ таким образом:
Покажем что вид $e_2$ не зависит от дополнительных членов при $\varphi_2$ в виде $ \widetilde{B}\varphi_0(x) + C$, а только зависит от $A$:

$\varphi_2(x) = (A \varphi_1(x) + \widetilde{B}\varphi_0(x) + C) e_1(x)$

так как $\varphi_0 e_i = e_i$

$\varphi_2(x) = (A \varphi_1(x) + B\varphi_0(x) + C) e_1(x) = (A \varphi_1(x) + B) e_1(x) $

где $B = \widetilde{B} + C$

таким образом подставляя $\varphi_2(x)$ в $(2)$:

$e_2 = (A \varphi_1(x) + B) e_1(x) - \alpha_2 e_0 - \beta_1 e_1$

$e_2 = A \varphi_1(x) - \alpha_2 e_0 - (\beta_1 - B) e_1$

получили:

$e_2 = A \varphi_1(x) - \alpha_2 e_0 - \widetilde{\beta_1} e_1$

находя коэффициенты $\alpha_2$ и $\widetilde{\beta_1}$ из:

$\begin{cases} (e_2, e_0) = 0 \\ (e_2, e_1) = 0 \\ \end{cases} $

получаем коэффицинты:

$ \\ \alpha_2 = A \frac{(\varphi_1 e_1, e_0)}{\|e_0\|^2}, \ \ \ \ \widetilde{\beta_1} = A \frac{(\varphi_1 e_1, e_1)}{\|e_1\|^2} $

и подставляя в предыдущее выражение для $e_2$ получаем:

$e_2 = A \varphi_1 e_1 - A \frac{(\varphi_1 e_1, e_1)}{\|e_1\|^2} e_1 - A \frac{(\varphi_1 e_1, e_0)}{\|e_0\|^2} e_0 \ \ \ (3)$

Теперь посчитаем квадрат нормы для начала для $e_0, e_1, e_2$ (где $e_1 = \varphi_1 - \frac{(\varphi_1, e_0)}{\|e_0\|^2} e_0$ ):

$(e_0, e_0) = \| \varphi_0 \|^2 $

$(e_1, e_1) = \| \varphi_1 \|^2 - [\frac{(\varphi_1, e_0)}{\|e_0\|}]^2 $

$(e_2, e_2) = A^2 \cdot ( \| \varphi_2 \|^2 - [\frac{(\varphi_1 e_1, e_0)}{\|e_0\|}]^2 - [\frac{(\varphi_1 e_1, e_1)}{\|e_1\|}]^2 ) $

$\ldots$

$(e_n, e_n) = A^2 \cdot ( \| \varphi_n \|^2 - \sum_{k=0}^{n-1} [\frac{(\varphi_1 e_{n-1}, e_k)}{\|e_k\|}]^2) $

Нормировка на единицу:

$(e_0, e_0) = C_0^2 \ \| \varphi_0 \|^2 = 1 $

$(e_1, e_1) = C_1^2 \ ( \| \varphi_1 \|^2 - [\frac{(\varphi_1, e_0)}{\|e_0\|}]^2 ) = 1 $

$(e_2, e_2) = A^2 \ ( \| \varphi_1 e_1 \|^2 - [\frac{(\varphi_1 e_1, e_0)}{\|e_0\|}]^2 - [\frac{(\varphi_1 e_1, e_1)}{\|e_1\|}]^2 ) = 1 $

$\ldots$

$(e_n, e_n) = C_n^2 \ ( \| \varphi_1 e_{n-1} \|^2 - \sum_{k=0}^{n-1} [\frac{(\varphi_1 e_{n-1}, e_k)}{\|e_k\|}]^2) = 1 $

Что дальше делать?
Откуда появляется право сделать равным единице коэффициент $ A $ в $ (3) $ и в рекуррентном соотношении, ниже? :

$e_{n+1} = A \varphi_1 e_n - A \frac{(\varphi_1 e_n, e_n)}{\|e_n\|^2} e_n - A \frac{(\varphi_1 e_n, e_{n-1})}{\|e_{n-1}\|^2} e_{n-1}$

[Евгений Машеров]

ktoto в сообщении #919394 писал(а):

В литературе всюду появляется рекуррентное соотношение для ортогональных многочленов:

${p_{n+1}(x)\ =\ (A_nx+B_n)\ p_n(x)\ -\ C_n\ p_{n-1}(x)}$

Каким образом приходят к данному выражению?

(Оффтоп)

"Царство Божие силою берётся!" (Евангелие от Матфея 11, 12.)

Оно нам оказывается нужным, и мы его "берём силой". Всегда можно ортогонализовать вновь добавляемую функцию ко всем уже имеющимся, процедурой Грама-Шмидта. Но это скучно и трудоёмко. Поэтому выражаем желание получать новую, ортогональную к имеющимся, малыми вычислительными усилиями, выражая её через не все уже полученные, а малое их число. По врождённой лени ограничиваемся линейными комбинациями функций. Чтобы новая функция стала полиномом степени на единицу выше - коэффициенты в линейной комбинации должны включать в себя x. Пытаемся получить новую $P_{n+1}$ только из $p_n$ - не выходит каменный цветокортогональность. Пытаемся скомбинировать две функции $p_n$ и $p_{n-1}$ - ура, получилось! При этом вновь полученная функция оказывается ортогональна не только к двум предшествующим, а ко всем ранее полученным. То есть мы получили требуемое.
Можно сохранить общность, оставив три коэффициента A, B, C, а можно заметить, что один из них лишний, от него зависит только нормировка, и можно все поделить на него. Очевидно, гарантировать, что он будет ненулевым, можно только для A, иначе степень $p_{n_1}$ не будет (n+1), стало быть, на него и делим.
Приходим к
${p_{n+1}(x)\ =\ (x+b_n)\ p_n(x)\ -\ b_n\ p_{n-1}(x)}$
$b=B/A$ $c=C/A$
и это выражение гарантирует, что если у $p_n$ старший коэффициент единица, то то же будет и у $p_{n+1}$, по построению.