1

I am working through some exam prep questions, and need a little guidance on this one:

The 2 point Gauss for weight $e^{-x}$ on the interval $[0, > \infty]$ has the form:

$$\int_{0}^{\infty}e^{-x}f(x)dx \approx w_1f(x_1) + w_2f(x_2)$$

(a) Use Gram-Schmidt to find the ortho polys $\phi_0(x)$, $\phi_1(x)$ and $\phi_2(x)$ for the weight function $w(x) = e^{-x}$ in $0 \le x\le \infty$ Find also $A_0$, $A_1$, $A_2$, $\gamma_0$, $\gamma_1$

(b) Determine $x_1$ and $x_2$ for 2-point Gauss from $\phi_2(x)$

(c) Use relation:

$$\phi_{k+1}(x)- (a_kx + b_k)\phi_k(x) + c_k\phi_{k-1}(x) = 0$$ express:

$$w_k = -\frac{A_{n+1}\gamma_n}{A_{n-1}\phi_{n+1}(x_k)\phi'_n(x_k)}$$ in the form:

$$w_k = \frac{A_{n}\gamma_{n-1}}{A_{n-1}\phi_{n-1}(x_k)\phi'_n(x_k)}$$

For part(a), using Gram-schmidt, I managed to calculate the ortho polys as:

$\phi_0(x) = 1$, $\phi_1(x) = $ and $\phi_2(x)= $ and hence $A_0 = A_1 = A_2 = 1$

Then I get that $\gamma_0 = <\phi_0,\phi_0> = 1$ and $\gamma_1 = <\phi_1,\phi_1> = 1$, which were calculated whilst working out the ortho poly.

However, I am stuck with parts (b) and (c) - my textbook has not given me any examples or formulas for the calculating the nodes from the orthogonal polynomials, nor have I any formulas for the weights.

On a broader note, I feel like I am just mechanically following procedures, but I don't really understand the relationship between these orthol polys and the original integral we are trying to approximate. Are they purely used to calculate the weight functions? I'm finding it difficult to understand how they relate.

Thanks so much in advance for any help you can give me.

JackReacher
  • 2,189

1 Answers1

1

The nodes of the $n$-point Gaussian quadrature are given by the zeros of the orthogonal polynomial $\phi_n(x)$. For your case, that would be the roots of $$ x^2 -4x + 2 = 0\\ x_{1,2} = 2 \pm \sqrt{2}. $$

Weights of an interpolating quadrature

Consider some arbitrary interpolating type quadrature with nodes $x_i$ and weights $w_i$. A quadrature is said to be interpolating if it exactly integrates an interpolating polynomial $P(x)$ passing through points $(x_i, f(x_i))$. Polynomial $P(x)$ could be expressed in terms of Lagrange interpolation basis $$ f(x) \sim P(x) = \sum_{i=1}^n f(x_i) \ell_i(x), \qquad \ell_i(x) = \frac{\prod_{j\neq i}(x-x_j)}{\prod_{j\neq i}(x_i-x_j)}. $$ Integrating the both sides gives a rule $$ \int_a^b f(x)\omega(x)dx \approx \int_a^b P(x)\omega(x)dx = \sum_i f(x_i) w_i\\ w_i \equiv \int_a^b \ell_i(x) \omega(x) dx. $$ So, for an interpolating type quadrature (which Gaussian quadratures are) the weights can be computed by integrating Lagrange basis functions $$ w_i = \int_a^b \ell_i(x) \omega(x) dx. $$ This formula would integrate every $f(x)$ precisely, provided that $f(x)$ is a polynomial of degree $n-1$, since $P(x)$ would just be $f(x)$ itself. Note that this holds whatever nodes $x_i$ we choose. So careful choice of $x_i$ may (and does) extend this property for higher polynomial degrees.

Relation between Gaussian quadratures and orthogonal polynomials

Consider some polynomial $f(x)$ with degree $m \geq n$. We can divide it by $(x-x_1)\cdots(x-x_n)$ polynomial $$ f(x) = q(x)(x-x_1)\cdots(x-x_n) + r(x),\qquad \operatorname{deg}(q) = m - n,\quad \operatorname{deg}(r) \leq n-1. $$ Applying quadrature rule to $f(x)$ yields $$ \int_a^b f(x) \omega(x) dx \approx \sum_{i=1}^n w_i f(x_i) = \sum_{i=1}^n w_i r(x_i). $$ Quadrature rule ignores $q(x)(x-x_1)\cdots(x-x_n)$ part since it vanishes as every node $x_i$. We want the same property for the integral $$ \int_a^b q(x)(x-x_1)\cdots(x-x_n)\omega(x) dx = 0 $$ for every polynomial $q(x)$ with its degree not exceeding some upper limit. Consider case when $x_i$ are roots of $\phi_n(x)$ orthogonal polynomial. Then $$ \phi_n(x) = A_n(x-x_1)\cdots(x-x_n) $$ and $q(x)$ can be expanded over basis of $\phi_0(x), \phi_1(x), \dots$: $$ q(x) = q_0 \phi_0(x) + q_1 \phi_1(x) + \dots $$ Now $$ \int_a^b q(x)(x-x_1)\cdots(x-x_n)\omega(x) dx = \frac{1}{C_n} \int_a^b q(x)\phi_n(x) \omega(x) dx = \frac{1}{C_n} \sum_{k > 0} q_k \langle \phi_k, \phi_n \rangle = \frac{q_n\gamma_n}{A_n}. $$ That integral would be zero if $q_n = 0$ which is true for every polynomial of degree less than $n$, i.e. $\operatorname{deg}(q) < n$ and $\operatorname{deg}(f) < n+n = 2n$.

Expressing weights without Lagrange basis functions

Observe that $$ \ell_i(x) = \frac{\prod_{j \neq i}(x - x_j)}{\prod_{j \neq i}(x_i - x_j)} = \frac{\phi_n(x)}{A_n(x-x_i)\prod_{j \neq i}(x_i - x_j)}. $$ Let's consider the $\phi_n'(x)$: $$ \phi_n'(x) = A_n\frac{d}{dx}\prod_{i=1}^n (x - x_i) = A_n\sum_{j=1}^n \prod_{i \neq j} (x - x_i). $$ At nodes only one term lefts from the sum: $$ \phi'_n(x_k) = A_n\sum_{j=1}^n \prod_{i \neq j} (x_k - x_i) = \prod_{i \neq k} (x_k - x_i). $$ Thus $$ \ell_i(x) = \frac{\phi_n(x)}{(x-x_i)\phi'_n(x_i)}\\ \int_a^b \ell_i(x) \omega(x) dx = \frac{1}{\phi'(x_i)}\int_a^b \frac{\phi_n(x)}{x-x_i} \omega(x) dx. $$ Now let's evaluate $\int_a^b \frac{\phi_n(x)}{x-x_i} \omega(x) dx$ using auxillary integral $$ \int_a^b \frac{\phi_n(x)}{x-x_i} [\phi_{n+1}(x)-\phi_{n+1}(x_i)] \omega(x) dx = \int_a^b \phi_n(x)\frac{\phi_{n+1}(x)-\phi_{n+1}(x_i)}{x-x_i} \omega(x) dx. $$ Since $\phi_{n+1}(x)-\phi_{n+1}(x_i)$ vanishes at $x = x_i$ by polynomial remainder theorem $\frac{\phi_{n+1}(x)-\phi_{n+1}(x_i)}{x-x_i}$ is a polynomial of degree $n$ with leading coefficient $A_{n+1}$. $$ \frac{\phi_{n+1}(x)-\phi_{n+1}(x_i)}{x-x_i} = \frac{A_{n+1}}{A_n} \phi_n(x) + \text{polynomial rest of degree } < n. $$ The polynomial $\phi_n(x)$ is orthogonal to the polynomial rest, auxiliary integral is $$ \int_a^b \frac{\phi_n(x)}{x-x_i} [\phi_{n+1}(x)-\phi_{n+1}(x_i)] \omega(x) dx = \frac{A_{n+1}}{A_n} \int_a^b \phi_n^2(x) dx = \frac{A_{n+1}}{A_n}\gamma_n\\ \int_a^b \frac{\phi_n(x)}{x-x_i} \phi_{n+1}(x) \omega(x) dx -\phi_{n+1}(x_i)\int_a^b \frac{\phi_n(x)}{x-x_i} \omega(x) dx = \frac{A_{n+1}}{A_n}\gamma_n. $$ On the other hand the integral $$ \int_a^b \frac{\phi_n(x)}{x-x_i} \phi_{n+1}(x) \omega(x) dx $$ is zero, because $\frac{\phi_n(x)}{x-x_i}$ is a polynomial of degree less than $n+1$. Finally $$ \int_a^b \frac{\phi_n(x)}{x-x_i} \omega(x) dx = -\frac{A_{n+1}\gamma_n}{A_n\phi_{n+1}(x_i)} $$ and $$ w_i = -\frac{A_{n+1}\gamma_n}{A_n\phi_{n+1}(x_i)\phi'_n(x_i)}. $$ This is the correct version of the first formula from (c). It can be easily seen that the formula should stay invariant under scaling of the polynomials $\phi_i(x)$, i.e. changing $A_k$ (note only that $\gamma_k \sim A_k^2$): $$ w_i \sim \frac{A_{n+1}A_n^2}{A_n A_{n+1} A_n} = 1. $$

Relation between recurrence coefficients $a_n, c_n$ and $A_k, \gamma_k$

We're given that $$ \phi_{n+1}(x) - (a_n x +b_n) \phi_n(x) + c_n \phi_{n-1}(x) = 0. $$ Plugging $x = x_i$ zeroes $\phi_n(x)$ so $$ \phi_{n+1}(x_i) = -c_n \phi_{n-1}(x_i). $$ Now we have to express $c_n$ using known values of $A_n$ and $\gamma_n$.

$$ 0 = \langle \phi_{n+1}(x) - (a_n x +b_n) \phi_n(x) + c_n \phi_{n-1}(x)\;,\; \phi_{n+1}(x) \rangle = \gamma_{n+1} - a_n \langle x \phi_n(x) , \phi_{n+1}(x) \rangle\\ 0 = \langle \phi_{n+1}(x) - (a_n x +b_n) \phi_n(x) + c_n \phi_{n-1}(x)\;,\; \phi_{n-1}(x) \rangle = c_n\gamma_{n-1} - a_n \langle x \phi_n(x) , \phi_{n-1}(x) \rangle\\ $$ Since $\langle x \phi_n(x) , \phi_{n-1}(x) \rangle = \langle \phi_n(x) , x\phi_{n-1}(x) \rangle$ we have $$ \gamma_{n+1} = a_n \langle x\phi_n , \phi_{n+1} \rangle\\ c_n\gamma_{n-1} = a_n \langle \phi_n, x \phi_{n-1} \rangle\\ \frac{\gamma_n}{a_{n-1}}= \langle \phi_n, x \phi_{n-1} \rangle = \frac{c_n \gamma_{n-1}}{a_n} $$ so $$ c_n = \frac{a_n}{a_{n-1}} \frac{\gamma_n}{\gamma_{n-1}}. $$ Notice that $A_{n+1} - a_n A_n$ is the coefficient of the $x^{n+1}$ term in recurrence, so $$ a_n = \frac{A_{n+1}}{A_n}. $$ Finally, $$ c_n = \frac{A_{n+1}A_{n-1}}{A_n^2} \frac{\gamma_n}{\gamma_{n-1}}\\ w_i = \frac{A_{n+1}\gamma_n}{A_n c_n \phi_{n-1}(x_i)\phi'_n(x_i)} = \frac{A_{n+1}A_n^2\gamma_n\gamma_{n-1}}{A_n A_{n+1}A_{n-1}\gamma_n \phi_{n-1}(x_i)\phi'_n(x_i)} = \frac{A_n\gamma_{n-1}}{A_{n-1} \phi_{n-1}(x_i)\phi'_n(x_i)}. $$

uranix
  • 7,503
  • Wow, thank you so very much for this comprehensive answer. I am reading through it carefully - I'm sure I will have a few follow up questions. – JackReacher May 31 '15 at 22:35
  • @JackReacher you're welcome. I will be able to see them in the morning, tomorrow. – uranix May 31 '15 at 22:39