---
title: ANL Lista 12
tags: ANL
author: Mateusz Reis
---
# ANL LISTA 12

## Zadanie 1


Mamy całkę
$$
\int_a^b g(x)dx
$$

użyjemy podstawienia (chemy aby $t(a)=-2$ oraz $t(b)=2$)
$$
\int_a^b g(x)dx =
\Bigg[
t=-2+4*\frac{x-a}{b-a}
,dt=\frac{4}{b-a}dx
\Bigg]=\\
\left[
x=\frac{t+2}{4}*(b-a)+a,dx=\frac{dt(b-a)}{4}
\right]=\\
\int_{-2}^2 g(\frac{t+2}{4}*(b-a)+a)*\frac{dt(b-a)}{4}=\\
\frac{(b-a)}{4}\int_{-2}^2 g(\frac{t+2}{4}*(b-a)+a)*dt
$$

Teraz możemy użyć procedury integral dla tak przekształconej całki.

## Zadanie 2

- $\implies$
Zakładamy że $rzad(Q_n)\geq n+1$ chcemy pokazać że $Q_n$ jest kwadraturą interpolcyjną
$$
L_n(x)=\sum_{i=0}^n \lambda_i(x)f(x_i)
$$
Niech
$$
f(x)=\lambda_i(x)\in \Pi_n\\
\lambda_i(x)=\Pi_{k=0\\k\not=i}^n\frac{x-x_k}{x_i-x_k}\\
\lambda(x_k)=0\\
\lambda(x_i)=1
$$
wtedy
$$
\int_a^b \lambda_i(x)dx=Q_n(\lambda_i(x))=\sum_{k=0}^nA_k\lambda_i(x_k)=\\
A_i\lambda(x_i)=A_i
$$
- $\Longleftarrow$
Załóżmy że $Q_n$ jest kwadraturą interpolcyjną, chcemy pokazać że $rzad(Q_n)\geq n+1$.
$$Q_n=\int_a^bL_n(x)dx$$
Niech $w(x)\in\Pi_n$
wtedy
$w(x)\equiv L_n(x)\implies rzad(Q_n)\geq n+1$ ponieważ dla $\forall f(x)\in\Pi_n$ kwadratura $Q_n$ jest dokładna.

## Zadanie 4

Przyjmujemy że wszystkie wartości $x_i$ mamy w tablicy ```x[n+1]```.
Wzór na $A_k$ możemy przedstawić w postaci
$$
A_k=\frac{1}{p_{n+1}^`(x_k)}\int_a^b\frac{p_{n+1}(x)}{(x-x_k)}dx\\
p_{n+1}=\Pi_{i=0}^n(x-x_i)
$$
Wystarczy że policzymy $p_{n+1}(x)$ raz tzn. przekształcimy go do postaci potęgowej:

p[n+2];
p[0]=1;
for i=1,i<=n+1,i++
    for j=i,j>0,j--
        p[j]-=x[i]*p[j-1];

kosztuje to $O(n^2)$, ale robimy to tylko raz.
Następnie aby obliczyć całkę dzielimy wielomian schematem Hornera co kosztuje nas $O(n)$

pn[n+1];
pn[n]=p[n];
for i=n-1,i>=0,i--
    pn[i]=p[i]+x[k]pn[i+1];

Całkę $\int_a^b$ równiż policzymy w $O(n)$:

suma=0;
sumb=0;
for i=1,i<=n,i++
    suma+=pn[i]*a^i/i;
    sumb+=pn[i]*b^i/i;
return sumb-suma;

Pozostało nam policzyć pochodną z $p_{n+1}$ w punkcie $x_k$
zrobimy to używając schematu Hornera dwa razy, po policzeniu pochodnej w punkcie $x_k$ zostanie nam tylko ostatni współczynnik.

Jeśli liczymy wszystkie współczynniki $A_k$ to łączny koszt algorytmu to $O(n^2)$ ponieważ policzenie postaci potęgowej kosztuje $O(n^2)$, mając to możemy obliczyć każdy wspołczynnik w czasi liniowym a mamy $n$ współczynników.

## Zadanie 5

Mamy wzór
$$
L_n(x)=\sum_{i=0}^n f(x_i)\Pi_{k=0}^n\frac{x-x_k}{x_i-x_k}=\{x_k=a+\frac{b-a}{n}k\}=\\
\sum_{i=0}^nf(x_i)\Pi_{k=0}^n\frac{x-a-\frac{b-a}{n}k}{a+\frac{b-a}{n}i-a-\frac{b-a}{n}k}=\{h=\frac{b-a}{n}\}=\\
\sum_{i=0}^n f(x_i)\Pi_{k=0}^n\frac{x-a-hk}{h(i-k)}=\{x=a+th\}=\\
\sum_{i=0}^n f(x_i)\Pi_{k=0}^n\frac{a+th-a-hk}{h(i-k)}=\sum_{i=0}^n f(x_i)\frac{t-k}{i-k}
$$

## Zadanie 7

$$
\frac{A_k}{b-a}=\frac{h}{b-a}\int_0^n\Pi_{j=0\\j\not=k}^n\frac{t-j}{k-j}dt\,\,\,\,\,\,h=\frac{b-a}{n}\\
\frac{A_k}{b-a}=\frac{1}{n}\int_{0}^{n}\Pi_{j=0\\j\not=k}^n\frac{t-j}{k-j}dt
$$

Wiemy że $n,k,j\in\mathbb{N}$ tak więc $\{\frac{1}{k-j},\frac{1}{n}\}\in\mathbb{Q}$
Policzmy całkę pomijając te wyrazy :
$$
\int_0^{n}\Pi_{j=0\\j\not=k}^n(t-j)dt=\\
\int_0^{n}\Big(t(t-1)(t-2)(t-3)...(t-k+1)(t-n)\Big)=\\
\int_0^n(a_{n-1}t^{n-1}+a_{n-2}t^{n-2}+...+a_0)dt=\\
\int_0^na_{n-1}t^{n-1}dt+\int_0^na_{n-2}t^{n-2}dt+...+\int_0^na_0dt=\\
a_{n-1}\frac{n^n}{n}+a_{n-2}\frac{n^{n-1}}{n-1}+...+a_0\frac{n}{1}
$$

Ponieważ $n\in\mathbb{N},a_i\in\mathbb{Z}$ całka jest liczbą wymierną jak i całe $A_i$