---

## Item XX

Explain how to obtain the nodes and weights for the Gaussian quadrature for from the Jacobi matrices.


---

The gaussian quadrature consists on approximating:

$$
\int_a^b f(x) \, dx \approx \sum_{j=1}^n w_j f(x_j)
$$

choosing the right $x_j$ and $w_j$ so that the approximation is perfect if $f$ is any polynomial of degree $2n-1$ or smaller.

**Lemma 1**: Being $\{p_j(x)\}_{j=0}^n$ a set of $n$ orthonormal polynomials where $\text{deg}(p_j) = j$. Then there exist a quadrature with nodes $\{x_k\}_{k=1}^n$ as the $n$ roots of $p_n$ that approximates perfectly any polynomial $f(x)$ of degree $2n-1$ or smaller.

*Proof*: By performing a [polynomial long division](https://en.wikipedia.org/wiki/Polynomial_long_division) of $f(x)$ over $p_n(x)$, we have that:
$$
f(x) = p_n(x) q(x) + r(x) \,,
$$
with $\text{deg}(r),\text{deg}(q) < n$.

So we have that:
\begin{align}
\int_a^b f(x) \, dx &= \underbrace{\int_a^b p_n(x) q(x) \,dx}_{= 0} + \int_a^b r(x) \,dx
\end{align}
We see that:
$$
\int_a^b p_n(x) q(x) \ = 0
$$
because $p_n \in \mathbb{P}^{n-1}$ which is part of the subspace generated by the base $\{p_j(x)\}_{j=0}^{n-1}$, and thus, orthogonal to $p_n(x)$.


By defining:
$$
L_j(x) = \prod_{i=1\\i\neq j}^n \frac{x-x_i}{x_j-x_i} \,,
$$
we have that:
\begin{align}
\int_a^b r(x) \,dx
&= \int_a^b \sum_{k=1}^n r(x_j) L_j(x) \,dx
\\ &= \sum_{k=1}^n \left( r(x_j) \underbrace{\int_a^b L_j(x) \,dx}_{=w_j} \right)
\\ &= \sum_{k=1}^n r(x_j) w_j
\end{align}
which corresponds with the quadrature. $\square$

Now, in order to build the orthonormal polynomials $\{p_j(x)\}_{j=0}^n$, so that $\text{deg}(p_j) = j$ we can use the following [recurrence relation](https://en.wikipedia.org/wiki/Gaussian_quadrature#Recurrence_relation):

\begin{align}
p_{r+1}(x) &= (x-a_{r})p_{r}(x)-b_{r}p_{r-1}(x)
\\ p_{-1}(x) &= 0 \,,
\end{align}
where:
$$
a_{r}:={\frac {\langle xp_{r},p_{r} \rangle}{ \langle p_{r},p_{r} \rangle}},\qquad b_{r}:={\frac {\langle xp_{r},p_{r-1} \rangle}{\langle p_{r-1},p_{r-1} \rangle}}={\frac {\langle p_{r},p_{r} \rangle}{\langle p_{r-1},p_{r-1} \rangle}} \,.
$$

Which can be rewritten as:

\begin{align}
x p_r(x) &= \beta_{r-1} p_{r-1}(x) + \alpha_r p_r(x) + \beta_r p_{r+1}(x)
\\ p_{-1}(x) &= 0
\end{align}

So, we have that:

\begin{align}
x \underbrace{\left( \begin{matrix}
p_0(x) \\
p_1(x) \\
p_2(x) \\
\vdots \\
p_{n-2}(x) \\
p_{n-1}(x) \\
\end{matrix} \right)}_{\mathbf{p}(x)} &= \underbrace{ \left( \begin{matrix}
a_0 & b_0 \\
b_0 & a_1 & b_1 \\
 & b_1 & a_2 & b_2 \\
 & & \ddots & \ddots & \ddots \\
 & & & b_{n-3} & a_{n-2} & b_{n-2} \\
 & & & & b_{n-2} & a_{n-1} \\
\end{matrix} \right)}_{T_n} \underbrace{\left( \begin{matrix}
p_0(x) \\
p_1(x) \\
p_2(x) \\
\vdots \\
p_{n-2}(x) \\
p_{n-1}(x) \\
\end{matrix} \right)}_{\mathbf{p}(x)} + b_{n-1} p_n(x) \underbrace{\left( \begin{matrix}
0 \\
0 \\
0 \\
\vdots \\
0 \\
1 \\
\end{matrix} \right)}_{\mathbf{e}_{n}} \\
x \mathbf{p}(x) &= T_n \mathbf{p}(x)+ b_{n-1} p_n(x) \mathbf{e}_n \,.
\end{align}

Making $x=x_j$ where $\{x_j\}_{j=1}^{n}$ are the roots of $p_n(x)$:
\begin{align}
x_j \mathbf{p}(x_j) &= T_n \mathbf{p}(x_j)+ b_{n-1} \underbrace{p_n(x_j)}_{=0} \mathbf{e}_n \\
x_j \mathbf{p}(x_j) &= T_n \mathbf{p}(x_j) \,,
\end{align}

which means that the roots of $p_n$ are the eigenvalues of this system, where $T_n$ is a tridiagonal (Jacobi) matrix. These roots also are the nodes of the Guassian quadrature due to the proven lemma.


```python

```

9faa2166b1f107951d54ac6f3ccee04cc4f37ec7
ipynb
Jupyter Notebook
t1_questions/item_20.ipynb
autopawn/cc5-works
63775574c82da85ed0e750a4d6978a071096f6e7
MIT
t1_questions/item_20.ipynb
autopawn/cc5-works
63775574c82da85ed0e750a4d6978a071096f6e7
MIT
t1_questions/item_20.ipynb
autopawn/cc5-works
63775574c82da85ed0e750a4d6978a071096f6e7
MIT
Qwen/Qwen-72B
1. YES
2. YES