405 lines
9.4 KiB
Typst
405 lines
9.4 KiB
Typst
#import "@preview/cetz:0.3.2";
|
|
#import "@preview/cetz-plot:0.1.1": plot
|
|
#import "@preview/physica:0.9.4": *
|
|
#import "@preview/plotsy-3d:0.1.0": plot-3d-parametric-surface
|
|
#import "@preview/fletcher:0.5.4" as fletcher: diagram, edge, node
|
|
|
|
#set page(paper: "a4", margin: (x: 2.6cm, y: 2.8cm), numbering: "1 : 1")
|
|
#set par(justify: true, leading: 0.52em)
|
|
|
|
#let FONT_SIZE = 18pt;
|
|
#set text(font: "FreeSerif", size: FONT_SIZE, lang: "us")
|
|
#show math.equation: set text(font: "Euler Math", size: (FONT_SIZE * 1.0), lang: "en")
|
|
|
|
#set heading(numbering: none)
|
|
#show heading.where(level: 1): it => {
|
|
rect(inset: FONT_SIZE / 2)[#it]
|
|
}
|
|
// #show heading.where(level: 2): it => [
|
|
// #set align(left)
|
|
// #set text(size: FONT_SIZE * 1.1, weight: "semibold")
|
|
// #(it.body)
|
|
// ]
|
|
|
|
#align(center)[
|
|
#text(size: FONT_SIZE * 2, weight: "bold")[#underline[exercise 2]]
|
|
]
|
|
|
|
these are my solutions to the second exercise set of TMA4135.
|
|
|
|
there should be a python source code file attached to this deliverable.
|
|
this file can be used to generate the images shown in problem 2.
|
|
|
|
this document was created using
|
|
#link("https://typst.app/")[#text(blue.darken(5%))[typst]].
|
|
|
|
#v(42pt)
|
|
|
|
#outline(title: none)
|
|
|
|
#v(42pt)
|
|
|
|
|
|
= problem 1
|
|
|
|
define the _cardinal functions_ as
|
|
$
|
|
ell_i(x) & := product_(j=0\ j!=i)^n (x - x_j) / (x_i - x_j) \
|
|
& = (x - x_0)/(x_i - x_0) dot dots.c dot
|
|
(x - x_(i-1))/(x_i - x_(i-1)) dot (x - x_(i+1))/(x_i - x_(i+1))
|
|
dot dots.c dot (x - x_n)/(x_i - x_n),
|
|
$
|
|
for $i = 0, ..., n$.
|
|
|
|
|
|
== a)
|
|
|
|
given $x_0 = -3, x_1 = -1, #[and] x_2 = 5$, then
|
|
#table(
|
|
$
|
|
l_0 & = product_(j=0\ j!=i)^n (x - x_j)/(x_0 - x_j) \
|
|
& = (x - x_1)/(x_0 - x_1) dot (x - x_2)/(x_0 - x_2) \
|
|
& = (x + 1)/(-2) dot (x - 5)/(-8) \
|
|
& = ((x + 1)(x - 5))/16 \
|
|
& = (x^2 - 4x - 5)/16
|
|
$,
|
|
$
|
|
l_1 & = product_(j=0\ j!=i)^n (x - x_j)/(x_1 - x_j) \
|
|
& = (x - x_0)/(x_1 - x_0) dot (x - x_2)/(x_1 - x_2) \
|
|
& = (x + 3)/(2) dot (x - 5)/(-6) \
|
|
& = ((x + 3)(x - 5))/(-12) \
|
|
& = (-x^2 + 2x + 15)/12
|
|
$,
|
|
$
|
|
l_2 & = product_(j=0\ j!=i)^n (x - x_j)/(x_2 - x_j) \
|
|
& = (x - x_0)/(x_2 - x_0) dot (x - x_1)/(x_2 - x_1) \
|
|
& = (x + 3)/(8) dot (x + 1)/(6) \
|
|
& = ((x + 3)(x + 1))/48 \
|
|
& = (x^2 + 4x + 3)/48
|
|
$,
|
|
|
|
column-gutter: 20%,
|
|
stroke: none,
|
|
columns: 3,
|
|
)
|
|
|
|
|
|
== b)
|
|
|
|
we can easily verify these cardinal functions
|
|
$
|
|
l_0(x_0) & = ((-3)^2 - 4(-3) - 5)/16 = (9 + 12 - 5)/16 = 1 \
|
|
l_0(x_1) & = ((-1)^2 - 4(-1) - 5)/16 = (1 + 4 - 5)/16 = 0 \
|
|
l_0(x_2) & = (5^2 - 4 dot 5 - 5)/16 = (25 - 20 - 5)/16 = 0 \
|
|
\
|
|
\
|
|
l_1(x_0) & = (-(-3)^2 + 2(-3) + 15)/12 = (-9 - 6 + 15)/12 = 0 \
|
|
l_1(x_1) & = (-(-1)^2 + 2(-1) + 15)/12 = (-1 -2 + 15)/12 = 1 \
|
|
l_1(x_2) & = (-5^2 + 2 dot 5 + 15)/12 = (-25 + 10 + 15)/12 = 0 \
|
|
\
|
|
\
|
|
l_2(x_0) & = ((-3)^2 + 4(-3) + 3)/48 = (9 - 12 + 3)/48 = 0 \
|
|
l_2(x_1) & = ((-1)^2 + 4(-1) + 3)/48 = (1 -4 + 3)/48 = 0 \
|
|
l_2(x_2) & = (5^2 + 4 dot 5 + 3)/48 = (25 + 20 + 3)/48 = 1
|
|
$
|
|
|
|
thus we see that they follow the desired pattern.
|
|
|
|
|
|
== c)
|
|
|
|
assume we have $n + 1$ data points, then
|
|
$
|
|
p_n(x) := sum_(i=0)^n y_i ell_i(x)
|
|
$
|
|
must be the (unique) interpolation polynomial for points $(x_i, y_i)$.
|
|
|
|
to show this, we first must convince ourselves that $deg(ell_i (x)) = n$.
|
|
recall the definition
|
|
$
|
|
ell_i(x) & := product_(j=0\ j!=i)^n (x - x_j) / (x_i - x_j) \
|
|
=> ell_i(x) & = product_(j=0\ j!=i)^n f(x)
|
|
$
|
|
where
|
|
$
|
|
f(x) = (x - x_j) / (x_i - x_j) \
|
|
=> deg(f(x)) = 1
|
|
$
|
|
|
|
the product contains exactly $n$ factors, because we iterate over the $n + 1$
|
|
data points, minus the one for $i = j$. thus, $deg(ell_i(x)) = n$.
|
|
|
|
lastly, we must verify that the interpolation condition holds for $p_n(x)$
|
|
$
|
|
p_n(x_i) = y_i, quad i = 0, ..., n.
|
|
$
|
|
|
|
we can expand the definition to show this
|
|
$
|
|
p_n(x_i) & = sum_(j=0)^n y_j ell_j(x_i) \
|
|
& = sum_(j=0)^n y_j product_(k=0\ k!=j)^n (x_i - x_k) / (x_j - x_k) \
|
|
& = sum_(j=0)^n y_j dot g(i, j)
|
|
$
|
|
where
|
|
$
|
|
g(i, j) := cases(
|
|
1 & quad "if" i = j,
|
|
0 & quad "otherwise"
|
|
)
|
|
$
|
|
|
|
thus we get
|
|
$
|
|
p_n(x_i) & = (sum_(j=0\ j!=i)^n y_j dot 0) + (sum_(j=0\ j=i)^n y_j dot 1) \
|
|
& = (0) + (y_i) = y_i
|
|
$
|
|
|
|
as such, we can see that $p_n(x)$ is the interpolation polynomial of the given
|
|
data points.
|
|
|
|
|
|
== d)
|
|
|
|
recall from a) that given $x_0 = -3, x_1 = -1, #[and] x_2 = 5$, then
|
|
#table(
|
|
$
|
|
l_0 = (x^2 - 4x - 5)/16
|
|
$,
|
|
$
|
|
l_1 = (-x^2 + 2x + 15)/12
|
|
$,
|
|
$
|
|
l_2 = (x^2 + 4x + 3)/48
|
|
$,
|
|
|
|
column-gutter: 20%,
|
|
stroke: none,
|
|
columns: 3,
|
|
)
|
|
|
|
let $y_0 = 8, y_1 = -4, #[and] y_2 = 12$. then using our proven formula from c),
|
|
we can compute the interpolation polynomial
|
|
$
|
|
p(x) & = sum_(j=0)^2 y_j ell_j(x) \
|
|
& = y_0 ell_0(x) + y_1 ell_1(x) + y_2 ell_2(x) \
|
|
& = (x^2 - 4x - 5)/2 + (x^2 - 2x - 15)/3 + (x^2 + 4x + 3)/4 \
|
|
& = (6x^2 - 24x - 30 + 4x^2 - 8x - 60 + 3x^2 + 12x + 9)/12 \
|
|
& = (13x^2 - 20x - 81)/12.
|
|
$
|
|
|
|
|
|
= problem 2
|
|
|
|
== a)
|
|
|
|
#image("x.png", width: 80%)
|
|
|
|
== b)
|
|
|
|
#image("y.png", width: 80%)
|
|
|
|
== c) & d)
|
|
|
|
#image("path.png", width: 80%)
|
|
|
|
#pagebreak()
|
|
|
|
= problem 3
|
|
|
|
let $y = f(x) := 2 + sin(x) cos(x)$ with
|
|
#[
|
|
#set align(center)
|
|
#set table(
|
|
stroke: (x, y) => {
|
|
if y == 0 { (bottom: luma(180)) }
|
|
if x == 0 { (right: luma(180)) }
|
|
},
|
|
inset: 10% + 5pt,
|
|
)
|
|
#table(
|
|
$i$, $0$, $1$, $2$,
|
|
$x_i$, $0$, $pi/6$, $pi/3$,
|
|
$y_i$, $2$, $2 + sqrt(3)/4$, $2 + sqrt(3)/4$,
|
|
columns: 4,
|
|
)
|
|
]
|
|
|
|
and define
|
|
$
|
|
p(x) := a_1 + a_2 sin x + a_3 sin 2x
|
|
$
|
|
where $p(x_i) = y_i #[for] i in {0, 1, 2} #[and] a_1, a_2, a_3 in RR$.
|
|
|
|
== a)
|
|
|
|
from some quick analysis, we can see that
|
|
$
|
|
a_1 = y_1 = 2 => \
|
|
sqrt(3)/4 = a_2/2 + sqrt(3) a_3 / 2 and \
|
|
sqrt(3)/4 = sqrt(3) a_2 / 2 + sqrt(3) a_3 / 2 => \
|
|
a_2/2 + sqrt(3) a_3 / 2 = sqrt(3) a_2 / 2 + sqrt(3) a_3 / 2 \
|
|
a_2 = sqrt(3) a_2 => a_2 = 0 => \
|
|
a_3 = 1/2
|
|
$
|
|
|
|
so we get $p(x) = 2 + 1/2 sin 2x$.
|
|
|
|
== b)
|
|
|
|
now, we can show that $p(x) = f(x)$, i.e. the error $e(x) = 0$
|
|
|
|
recall that
|
|
$
|
|
sin 2x = 2 sin x cos x
|
|
$
|
|
|
|
we then get
|
|
$
|
|
p(x) & = 2 + 1/2 sin 2x \
|
|
& = 2 + 1/2 (2 sin x cos x) \
|
|
& = 2 + sin x cos x = f(x)
|
|
$
|
|
as expected.
|
|
|
|
= problem 4
|
|
|
|
define
|
|
$
|
|
c_0 := y_0, quad
|
|
p_0(x) := c_0
|
|
$
|
|
and recursively
|
|
$
|
|
c_k & := (y_k - p_(k-1)(x_k))/(product_(i=0)^(k-1) (x_k - x_i)), \
|
|
p_k (x) & := p_(k-1)(x) + c_k product_(i=0)^(k-1) (x-x_i),
|
|
$
|
|
for $k = 1, ..., n$.
|
|
|
|
== a)
|
|
|
|
given data points
|
|
#[
|
|
#set align(center)
|
|
#set table(
|
|
stroke: (x, y) => {
|
|
if y == 0 { (bottom: luma(180)) }
|
|
if x == 0 { (right: luma(180)) }
|
|
},
|
|
inset: 10% + 5pt,
|
|
)
|
|
#table(
|
|
$i$, $0$, $1$, $2$,
|
|
$x_i$, $-1$, $1$, $5$,
|
|
$y_i$, $6$, $-2$, $4$,
|
|
columns: 4,
|
|
)
|
|
]
|
|
|
|
compute $p_2(x)$.
|
|
|
|
first we need
|
|
$
|
|
p_1(x) & = p_0(x) + (y_1 - p_0(x_1))/(x_1 - x_0) dot (x - x_0) \
|
|
& = 6 + (-2 - 6)/(1 - (-1)) dot (x - (-1)) \
|
|
& = 6 - 4 (x + 1) = -4x + 2
|
|
$
|
|
then use $p_1(x)$ in
|
|
$
|
|
p_2(x) & = p_1(x) + (y_2 - p_1(x_2))/((x_2 - x_0)(x_2 - x_1))
|
|
dot (x - x_0)(x - x_1) \
|
|
& = -4x + 2 + (4 - (-4)dot 4 + 2)/((5-(-1))(5-1))
|
|
dot (x - (-1))(x - 1) \
|
|
& = -4x + 2 + 11/12 dot (x + 1)(x - 1) \
|
|
& = 11/12 x^2 - 4x + 13/12
|
|
$
|
|
|
|
#linebreak()
|
|
|
|
== b)
|
|
|
|
$p_k (x)$ is the interpolation polynomial for the data points, because
|
|
#[ #set math.equation(numbering: "(1)", supplement: none)
|
|
$
|
|
deg(p_k (x)) = k quad forall quad k in NN quad
|
|
$ <p1>
|
|
and
|
|
$
|
|
p_k (x_i) = y_i quad forall quad i = 0, ..., k quad
|
|
$ <p2>
|
|
]
|
|
|
|
to show @p1, we can see from the definition that the product has degree $k$,
|
|
because there are $k$ factors containing $x$. by inductive argument, we can
|
|
trivially see that $p_(k-1) (x)$ must have a degree equal to $k-1$. as such,
|
|
$
|
|
deg(p_k (x)) = k
|
|
$
|
|
|
|
next, (@p2) can be shown by a splitting the problem into two cases, one of them
|
|
requiring induction, otherwise just direct proofs. observe
|
|
$
|
|
p_k (x_k) & = p_(k-1) (x_k) + c_k product_(i=0)^(k-1) (x_k - x_i) \
|
|
& = cancel(p_(k-1) (x_k)) + (y_k - cancel(p_(k-1) (x_k)))/cancel(
|
|
product_(i=0)^(k-1) (x_k
|
|
- x_i)
|
|
) dot cancel(product_(i=0)^(k-1) (x_k - x_i)) \
|
|
& = y_k.
|
|
$
|
|
thus (@p2) holds for $x_k$. to show that it holds for $x_j$ where $j < k$
|
|
requires that we analyze the product in the definition:
|
|
$
|
|
product_(i=0)^(k-1) (x_j - x_i)
|
|
$
|
|
but since $j in {0, ..., k - 1}$, the product must contain a $0$-factor for any
|
|
chosen $j$, thus canceling the entire second term of the definition, leaving us
|
|
with
|
|
$
|
|
p_k (x_j) & = p_(k-1) (x_j).
|
|
$
|
|
then we need to show that
|
|
$
|
|
p_(k-1) (x_j) & = y_j quad forall quad j in {0, ..., k - 1}
|
|
$
|
|
|
|
let us perform an inductive argument. the hypothesis is
|
|
$
|
|
p_0 (x_j) = y_j
|
|
$
|
|
|
|
this is wrong.
|
|
|
|
== c)
|
|
|
|
we can use the points from a) to form a scheme
|
|
|
|
#[
|
|
#set align(center)
|
|
#set table(
|
|
stroke: (x, y) => {
|
|
if x == 0 { (right: luma(180)) }
|
|
},
|
|
inset: 10% + 5pt,
|
|
)
|
|
#table(
|
|
$x_0 = -1$, $y_(0,0) = 6$, none, none,
|
|
none, none, $y_(0,1) = -4$, none,
|
|
$x_1 = 1$, $y_(1,1) = -2$, none, $y_(0, 2) = 13 slash 12$,
|
|
none, none, $y_(1,2) = 3 slash 2$, none,
|
|
$x_2 = 5$, $y_(2,2) = 4$, none, none,
|
|
columns: 4,
|
|
)
|
|
]
|
|
|
|
then we can form the interpolation polynomial according to the formula
|
|
$
|
|
p_k (x) = sum_(i=0)^k y_(0, i) product_(j=0)^(i-1) (x-x_j)
|
|
$
|
|
such that for $n + 1 = 3$ we get
|
|
$
|
|
p_n (x) = p_2(x) & = 6 - 4(x - (-1)) + 13/12 (x - (-1))(x - 1) \
|
|
& = 6 - 4x - 4 + 13/12 (x^2 - 1) \
|
|
& = 13/12 x^2 - 4x + 11/12
|
|
$
|
|
which is _almost_ what we got in a) suggesting that i've made a slight error in
|
|
either task.
|