\documentclass[a4paper, swedish, twoside, righttag, intlim]{article}
\frenchspacing
\usepackage{babel}
%\usepackage[isolatin1]{inputenc}
\usepackage{isolatin1}
\usepackage{amstex,amssymb}
\usepackage{theorem}

\title{Tillämpad matematik: Splineapproximation}
\author{Niels Möller}

\setcounter{secnumdepth}{1}

%borde finnas med i amstex paketet
\newcommand{\eqref}[1]{(\ref{#1})}
\newtheorem{lemma}{Lemma}
\newenvironment{proof}{\bigskip\noindent\textbf{Bevis}\quad}{\quad$\Box$\bigskip}
\newenvironment{result}[1]{\bigskip\noindent\textbf{#1}}{\bigskip}

% Makron
\newcommand{\ordo}[1]{\mathcal{O}\left(#1\right)}
\newcommand{\norm}[1]{\parallel #1 \parallel}

\begin{document}
\maketitle

\vspace*{\stretch{1}}

\begin{abstract}
  Jag löser problemet att anpassa en jämn kurva till punkterna
  $(x_k,y_k)$ genom att minimera
  \begin{equation*}
    \int_a^b (u''(x))^2 dx + \lambda \sum_{k=1}^n (u(x_k)-y_k)^2
  \end{equation*}
  Det visar sig att optimalt $u$ är en kubisk spline på $[x_1,x_n]$,
  med naturliga randvillkor. Då $\lambda \to 0$ närmar sig kurvan rät
  linje, som i minstakvadratmening approximerar punkterna. Då
  $\lambda \to \infty$ närmar sig kurvan en interpolerande spline.
\end{abstract}

\vspace*{\stretch{1}}


\tableofcontents

\vfill

\section{Problemställning}
Problemet är att finna en reellvärd funktion $u$ som minimerar
\begin{equation}
  \label{eq:J}
  J(u) = \int_a^b (u''(x))^2 dx + \lambda \sum_{k=1}^n
  (u(x_k)-y_k)^2
\end{equation}
där $(x_k,y_k)$ är $n$ givna punkter, $a<x_1<x_2< \dots <x_n<b$, och
$\lambda>0$. Man måste förstås också specificera över vilket rum av
$u$:n man vill minimera $J$. Jag betraktar $U=$ mängden av alla $u$
sådana att
\begin{itemize}
\item $u$ är kontinuerligt deriverbar på $[a,b]$,
\item $u'$ är absolutkontinuerlig (vilket medför att $u''$ existerar
  nästan överallt),
\item $u'' \in \mathcal{L}^2$.
\end{itemize}
$U$ är förstås ett vektorrum. 

Den första uppgiften är att visa att $J(u)$ verkligen har ett minimum
i $U$. Därefter visar jag att den minimerande funktionen är en spline
och att den är entydigt bestämd. Givet punkterna $(x_k,y_k)$ kan den
minimerande funktionen för varje $\lambda$ bestämmas ur ett linjärt
ekvationssystem, vilket används för att undersöka vad som händer i
gränsfallen $\lambda \to 0$ och $\lambda \to \infty$.


\section{Existens}
\label{sec:existens}

Jag använder i detta avsnitt beteckningarna
\begin{align*}
  (u,v) &= \int_a^b u'' v'' + \lambda \sum_{k=1}^n u(x_k)v(x_k) \\
  \norm{u} &= \sqrt{(u,u)}
\end{align*}
för $u,v \in U$. Definiera också en linjär avbildning $\sigma:
\mathcal{C}[x_1,x_n] \to \Bbb{R}^n$ genom
\begin{equation}
  \label{eq:sigma}
  \sigma(u) = (u(x_1), \dots, u(x_n))
\end{equation}
Då är
\begin{equation}
  \label{eq:norm}
  \norm{u}^2 = \norm{u''}_2^2 + \lambda \norm{\sigma(u)}^2
\end{equation}
där normerna i högerledet är vanlig $2$-norm på $\mathcal{L}^2[a,b]$
och $\Bbb{R}^n$.

Vi har, för alla $u,v \in U$, att
\begin{equation}
  \label{eq:konvex}
  J(u+v) = J(u) + J(v) + 2 (u,v) - \lambda \sum_{k=1}^n y_k^2
\end{equation}

\begin{lemma}
  \label{l:existens}
  Det finns en funktion $u^* \in U$ sådan att $J(v) \geq J(u^*)$, för
  alla $v \in U$.
\end{lemma}

\begin{proof}
  Låt $J^* = \inf_{v \in U} J(v)$. Eftersom $J(v) \geq 0$ för alla $v
  \in U$ så är $J^* \geq 0$. Låt $\{u_i\} \subset U$ vara en följd
  sådan att 
  \begin{equation}
    \label{eq:inf}
    \lim_{i \to \infty} J(u_i) = J^*
  \end{equation}
  Jag visar att denna följd konvergerar mot en funktion $u^* \in U$,
  och att detta $u^*$ uppfyller $J(u^*) = J^*$. Ekvation
  \eqref{eq:konvex} ger, med $u=(u_i+u_j)/2$ och $v=\pm(u_i-u_j)/2$,
  att
  \begin{align*}
    \frac{J(u_i)+J(u_j)}{2} &= J\left(\frac{u_i+u_j}{2}\right) +
    \norm{u_i-u_j}^2 \\
    &\geq J^* + \norm{u_i-u_j}^2
  \end{align*}
  där vi i den sista olikheten har utnyttjat att $J(u) \geq J^*$ för alla
  $u \in U$, och speciellt för $(u_i+u_j)/2$. Eftersom $J(u_i), J(u_j) \to
  J^*$ får vi
  \begin{equation}
    \label{eq:lim1}
    \norm{u_i-u_j} \to 0 \text{ då $i,j \to \infty$}
  \end{equation}
  Detta betyder enligt~\eqref{eq:norm} att $u_i''$ är en cauchyföljd i
  $\mathcal{L}^2[a,b]$, och att $\sigma(u_i)$ är en cauchyföljd i
  $\Bbb{R}^n$. Eftersom $\mathcal{L}^2[a,b]$ och $\Bbb{R}^n$
  är fullständiga finns det därför $f \in \mathcal{L}^2[a,b]$ och $\eta
  \in \Bbb{R}^n$ så att
  \begin{align}
    \label{eq:konv_L2}
    u_i'' &\to f \text{ i $\mathcal{L}^2$} \\
    \label{eq:konv_punkt_k}
    u_i(x_k) &\to \eta_k
  \end{align}
  Eftersom intervallet $[a,b]$ är begränsat medför \eqref{eq:konv_L2}
  att $u_i'' \to f$ i $\mathcal{L}^1$ så att vi kan definiera
  \begin{align*}
    g_i(x) &= \int_{x_1}^x u_i''(\xi) d\xi \\
    g(x) &= \int_{x_1}^x f(\xi) d\xi 
  \end{align*}
  Genom denna definition blir $g$ absolutkontinuerlig, och
  \begin{equation*}
    |g(x) - g_i(x)| \leq \int_a^b |f(\xi) - u_i''(\xi)| \to 0
  \end{equation*}
  så att $g_i \to g$ likformigt. Låt $C_1,C_2$ vara två konstanter och
  sätt
  \begin{equation*}
    u^*(x) = C_1 + C_2(x-x_1) + \int_{x_1}^x g(\xi) d\xi
  \end{equation*}
  Det är klart $u^* \in U$ och att $\norm{{u^*}'' - u_i''}_2 \to 0$,
  eftersom ${u^*}'' = f$. Nu ska vi välja $C_1,C_2$ så att även
  $\norm{\sigma(u^*-u_i)} \to 0$. För alla $x \in [a,b]$ gäller
  \begin{equation*}
    u(x)-u_i(x) = C_1 - u_i(x_1) + (C_2 - u_i'(x_1))(x-x_1) + \int_{x_1}^x
    (g(\xi)-g_i(\xi)) d\xi  
  \end{equation*}
  Integralen ovan går mot noll då $i \to \infty$ eftersom $g_i \to g$
  likformigt. Vi vet också att $u_i(x_k) \to \eta_k$. Sätt nu in
  $x=x_n$. Då \emph{följer} att $\lim u_i'(x_1)$ existerar. Välj
  $C_1 = \lim_{i \to \infty} u_i(x_1) = \eta_1$ och $C_2 = \lim_{i
    \to \infty} u_i'(x_1)$. Då gäller
  \begin{equation*}
    u_i(x) \to u^*(x) \text{ för alla $x \in [a,b]$}
  \end{equation*}
  och ur \eqref{eq:konv_punkt_k} fås
  \begin{equation*}
    u^*(x_k) = \lim_{i \to \infty} u_i(x_k) = \eta_k
  \end{equation*}

  Nu återstår bara att visa att $J(u^*) = J^*$. Men det följer av att
  normerna i \eqref{eq:norm} är kontinuerliga, tillsammans med
  \eqref{eq:konv_L2} och \eqref{eq:konv_punkt_k}.
% $u^* \in U$ ger att $J(u^*) \geq J^*$, och
%  Fatous lemma ger att
%  \begin{align*}
%    J(u) &= \int_a^b f^2 + \lambda \sum_{k=1}^n (\eta_k - y_k)^2 \\
%    &= \int_a^b \liminf_{i \to \infty} (u_i'')^2 + \lambda
%    \sum_{k=1}^n \left(\lim_{i \to \infty} u_i(x_k) - y_k\right)^2 \\
%    &\leq \liminf_{i \to \infty} \int_a^b (u_i'')^2 + \lambda lim_{i \to
%      \infty} \sum_{k=1}^n (u_i(x_k) - y_k)^2 \\
%    &= \lim_{i \to \infty} J(u_i) \\
%    &= J^*
%  \end{align*}
  Alltså är $J(u^*) = J^* \leq J(v)$, för alla $v \in U$. 
\end{proof}

Nästa steg är att visa att denna funktion $u^* \in U$ i själva verket
ligger i ett betydligt mindre rum.


\section{Variationsräkning}
\label{sec:variation}

Antag att $u \in U$ minimerar $J(u)$. Låt $\phi \in
\mathcal{C}^{\infty}[a,b]$ vara godtyckligt, och betrakta $I(\alpha) =
J(u+\alpha \phi)$. Eftersom $u$ är optimal och $u+\alpha\phi \in U$
för alla $\alpha$ så har $I(\alpha)$ ha ett minimum vid $\alpha=0$.
Eftersom $I(\alpha)$ är ett andragradspolynom i $\alpha$, så följer
\begin{equation}
  \label{eq:variation1} 
  0 = I'(0) = 2 \int_a^b u''(x) \phi''(x) dx + 2\lambda \sum_{k=1}^n
  (u(x_k)-y_k)\phi(x_k)
\end{equation}
Då $u'$ är absolutkontinuerlig kan vi partialintegrera. Vi begränsar
oss ett tag till sådana $\phi$ som har stöd i det öppna intervallet
(a,b). Då ger \eqref{eq:variation1} efter två partialintegrationer att
\begin{equation*}
  0=\int_a^b u(x) \phi^{(4)}(x) dx + \lambda \sum_{k=1}^n
  (u(x_k)-y_k)\phi(x_k)
\end{equation*}
Om $u$ betraktas som en distribution på $(a,b)$ betyder det att
\begin{equation*}
  u^{(4)}+ \lambda  \sum_{k=1}^n(u(x_k)-y_k) \delta_{x_k} = 0 \ \text{i distributionsmening.}
\end{equation*}
Integrera, och låt $h$ beteckna funktionen
\begin{equation*}
  h(x) =
  \begin{cases}
    0 &\text{om $x<0$} \\
    1 &\text{om $x>0$} 
  \end{cases}
\end{equation*}
Då är 
\begin{equation}
  \label{eq:variation2}
  u^{(3)}+ \lambda  \sum_{k=1}^n(u(x_k)-y_k) h(x-x_k) = \text{konstant}
\end{equation}
Tydligen är $u^{(3)}$ styckvis konstant, diskontinuerlig endast i
punkterna $x_k$. Genom att integrera ännu ett par gånger ser vi att
$u''$ är kontinuerlig och styckvis linjär, så att $u$ är kontinuerligt
deriverbar två gånger, och på varje intervall $(a,x_1), (x_1,x_2),
\dots, (x_n,b)$ är $u(x)$ ett tredjegradspolynom.

Lämna nu begränsningen att $supp(\phi) \subset (a,b)$. Låt $\phi \in
\mathcal{C}^{\infty}[a,b]$ ha stöd i $[a,x_1)$. Vi vet enligt
ovan att $u''$ är linjär på $[a,x_1]$, så att $u''=C x + D$ för $a
\leq x \leq b$. \eqref{eq:variation1} ger
\begin{equation*}
  \begin{split}
    0 &= \int_a^b u'' \phi'' + \lambda
    \sum_{k=1}^n(u(x_k)-y_k)\phi(x_k) \\
      &= \int_a^{x_1}(C x + D) \phi''(x) dx \\
      &= [(C x + D) \phi'(x) - C \phi(x)]_a^{x_1} \\
      &= - (C a + D) \phi'(a) + C \phi(a)
  \end{split}
\end{equation*}
Eftersom likheten ska gälla för alla $\phi$, och därmed för alla
värden på $\phi(a)$ och $\phi'(a)$, så följer att $C=D=0$. Alltså är
$u''=0$ för $a \leq x \leq x_1$. Samma resonemang ger att $u''=0$ för
$x_n \leq x \leq b$.

Vi har alltså följande
\begin{lemma}
  \label{l:spline}
  Antag att $u \in U$, och att $u$ minimerar $J(u)$. Då gäller
  \begin{itemize}
  \item $u \in \mathcal{C}^2[a,b]$,
  \item $u$ är på varje intervall $[x_k, x_{k+1}]$ ett polynom av grad
    högst tre,
  \item $u$ är linjär på intervallen $[a,x_1]$ och $[x_n,b]$.
  \item Speciellt är $u''(x_1)=u''(x_2) = 0$.
  \end{itemize}
  Med andra ord är $u$ en kubisk spline på $[x_1,x_n]$, med naturliga
  randvillkor.
\end{lemma}

Genom att sätta in $u^{(3)}(x) = 0$ för $x<x_1$ och $x>x_n$ i
  \eqref{eq:variation2} ser vi också att
\begin{equation*}
  \sum_{k=1}^n u(x_k) = \sum_{k=1}^n y_k
\end{equation*}
vilket är ganska naturligt. I själva verket ger \eqref{eq:variation2}
och lemma \ref{l:spline} tillräcklig information för att ställa upp
ett linjärt ekvationssystem för tredjegradspolynomens koefficienter.
Men för att besvara frågor om lösningens struktur, om dess entydighet,
och om inverkan av olika val av $\lambda$, är denna ``lösning'' av
problemet inte till stor hjälp.


\section{Vektorrumsstruktur}
\label{sec:rum}

Låt $W=$ mängden av alla $u \in \mathcal{C}^2[a,b]$ sådana att
\begin{itemize}
\item $u$ på varje intervall $[x_k, x_{k+1}]$ är ett polynom av högst
  grad tre,
\item $u$ är linjär på intervallen $[a,x_1]$ och $[x_n,b]$.
\end{itemize}
$W$ är ett linjärt underrum av $U$, och lemma~\ref{l:spline} säger
precis att varje optimalt $u \in U$ i själva verket ligger i $W$. För
att visa att den minimerande funktionen är entydigt bestämd räcker det
därför visa entydighet under det extra villkoret att $u \in W$.

Ett element i $u \in W$ är entydigt bestämt av de $n$ talen
\begin{equation*}
u(x_1), u''(x_2), \dots, u''(x_{n-1}), u(x_n)
\end{equation*}
I avsnitt~\ref{sec:bas} används detta för att konstruera en bas för
$W$ med $n$ element. Det följer då att $dim(W)=n$.

$W \subset \mathcal{C}^2[a,b]$, men vi kan också betrakta $W$ som ett
underrum av $\mathcal{C}^2[x_1,x_n]$, genom att identifiera varje
element i $W$ med dess restriktion till $[x_1,x_n]$. För om två
element i $W$ är lika på $[x_1,x_n]$ så är de lika på hela $[a,b]$,
eftersom de är kontinuerligt deriverbara, och linjära på $[a,x_1]$ och
$[x_n,b]$.

Nu bäddar vi in $W$ i ett större vektorrum, genom att ta bort kravet
att derivatorna ska vara kontinuerliga. Låt $V=$ mängden av alla $u
\in \mathcal{C}[x_1,x_n]$ sådana att $u$ på varje intervall
$[x_k,x_{k+1}]$ är ett polynom av grad högst tre. $V$ är ett
ändligdimensionellt vektorrum; man ser lätt att dimensionen är högst
$4 (n-1)$. $W$ är ett linjärt underrum av $V$ (om vi identifierar
elementen i $W$ med sina restriktioner till $[x_1,x_n]$). Däremot
gäller förstås varken $V \subset U$ eller $U \subset V$.


\section{Skalärprodukt}
\label{sec:inre_produkt}

Nästa mål är att beskriva funktionalen $J$ med hjälp av en
skalärprodukt på ett hilbertrum. Vi behöver därför en skalärprodukt på
$V$. Denna skalärprodukt kommer att bero av $\lambda$, eftersom $J$
gör det, men vi kan bygga upp den av $\lambda$-oberoende delar.

Vi börjar med att undersöka avbildningen $\sigma: u \to (u(x_1),
\dots, u(x_n)$, som definierades i avsnitt~\ref{sec:existens}.
$\sigma$ är förstås inte injektiv på $V$, eftersom $\Bbb{R}^n$ har
lägre dimension än $V$. Men $dim \ W = dim \ \Bbb{R}^n$. Detta,
tillsammans med följande lemma, visar att restriktionen av $\sigma$
till $W$ är bijektiv.
\begin{lemma}
  \label{l:iso}
  $\sigma$ är injektiv på $W$.
\end{lemma}
\begin{proof}
  Antag att $v \in W$ och att $v(x_1)= \dots = v(x_n)=0$. Vi behöver
  visa att detta medför $v=0$.

  Eftersom $v \in W$ är $v''(x_1)=0$. Om även $v'(x_1)=0$ måste $v(x)
  = c(x-x_1)^3$ för $x_1 \leq x \leq x_2$, och $v(x_2)=0$ ger att
  $v=0$ på $[x_1,x_2]$. Då är även $v'(x_2)=v''(x_2)=0$, och induktion
  ger $v=0$ på hela $[x_1,x_n]$.
  
  Om vi i stället har $v'(x_1) \neq 0$ så måste $v'(x_2)$ och
  $v''(x_2)$ vara nollskilda och ha samma tecken, eftersom $v(x_1) =
  v(x_2) = 0$ och $v$ är ett tredjegradspolynom på $[x_1,x_2]$, med
  inflexionspunkt i $x_1$. På $[x_2,x_3]$ uppfyller därför $v$
  \begin{itemize}
  \item $v(x_2) = v(x_3) = 0$,
  \item $v'(x_2)$ och $v''(x_2)$ är nollskilda, och har samma tecken,
  \item $v$ är ett tredjegradspolynom.
  \end{itemize}
  Då måste även $v'(x_3)$ och $v''(x_3)$ vara nollskilda och ha samma
  tecken. Induktion ger att $v''(x_k) \neq 0$ för alla
  $k=2,3,\dots,n$.

  Men $v''(x_n)=0$, eftersom $v \in W$. Denna motsägelse visar att
  $v'(x_1) \neq 0$ är omöjligt, och det följer att $v'(x_1)=0$, och
  därmed $v=0$, vilket avslutar beviset.
\end{proof}

Lemmat medför att det finns ett entydigt bestämt $s \in W$ sådant att
$\sigma(s) = (y_1,\dots,y_n)$. Detta $s$ är den kubiska spline med
naturliga randvillkor som interpolerar punkterna $(x_k,y_k)$. Vi
kommer att behöva denna funktion igen i avsnitt~\ref{sec:granser}.

Nu kan vi definiera ett par ickenegativa bilinjära former på $V$. Låt
$u,v \in V$ och sätt
\begin{gather*}
  u \cdot v = \sigma(u) \cdot \sigma(v) = \sum_{k=1}^n u(x_k) v(x_k) \\
  (u,v)_0 = \int_{x_1}^{x_n} u''(x) v''(x) dx = \sum_{k=1}^{n-1}
  \int_{x_k}^{x_{k+1}} u''(x) v''(x) dx \\
  (u,v)_{\lambda} = (u,v)_0 + \lambda u \cdot v \\
  \norm{u}_{\lambda} = \sqrt{(u,u)_{\lambda}}
\end{gather*}
Observera att det \emph{inte} är samma norm och skalärprodukt som i
avsnitt~\ref{sec:existens}.

Lemma~\ref{l:iso} ger att $u \cdot v$ är positivt definit på $W$.
Dessutom är $(u,v)_{\lambda}$ positivt definit på hela $V$. För anta
att $(u,u)_{\lambda}=0$. Då måste $u \cdot u = (u,u)_0=0$. Av
$(u,u)_0=0$ följer att $u''=0$ och $u$ är linjär på varje intervall
$[x_k,x_{k+1}]$. Då medför $u \cdot u = 0$ att $u=0$ på $[x_1,x_n]$.

Eftersom $V$ har ändlig dimension så är $V$ fullständigt med avseende
på \emph{varje} skalärprodukt. Alltså är $V$ ett hilbertrum, med
skalärprodukten $(u,v)_{\lambda}$. Av ändligdimensionaliteten följer
också att $W$ är ett slutet underrum i $V$.

Vi kommer flera gånger att använda följande egenskap hos
$(u,v)_{\lambda}$: Om $u''=0$ så är $(u,v)_{\lambda} = \lambda u \cdot
v$.

Låt nu $f$ vara den funktion som interpolerar punkterna $(x_k,y_k)$
linjärt. Med $h_k = x_{k+1}-x_k$ är
\begin{equation*}
  f(x) = y_k + \frac{1}{h_k}(x-x_k)(y_{k+1}-y_k) \text{ för $x_k \leq x \leq
  x_{k+1}$}
\end{equation*}
Eftersom $f''=0$ får vi nu, för alla $u \in W$,
\begin{equation*}
  \begin{split}
    \norm{u-f}_{\lambda}^2 &= \int_{x_1}^{x_n}
    (u''(x)-f''(x))^2 dx + \lambda \sum_{k=1}^n (u(x_k)-f(x_k))^2 \\
    &= \int_{x_1}^{x_n} (u''(x))^2 dx + \lambda \sum_{k=1}^n
    (u(x_k)-y_k)^2 \\ 
    &= J(u)
  \end{split}
\end{equation*}
Denna beskrivning av $J$, tillsammans med lemma~\ref{l:existens} och~
\ref{l:spline}, ger
\begin{lemma}
  \label{l:entydighet}
  Det finns ett entydigt bestämt $u^* \in U$ som minimerar $J(u)$,
  nämligen den ortogonala projektionen av $f$ i $W$ med avseende på
  skalärprodukten $(u,v)_{\lambda}$.
\end{lemma}


\section{Projektion}
\label{sec:projektion}

Vi kan dela upp $W$ i två ortogonala underrum. Låt $L=$ rummet av alla
linjära funktioner på $[x_1,x_n]$. Låt, för varje $u \in V$, $P(u)$
vara den ortogonala projektionen av $u$ i $L$. $P(u)$ är entydigt
bestämd av att
\begin{equation*}
  (P(u),l)_{\lambda} = (u,l)_{\lambda} \ \text{för alla $l \in L$}
\end{equation*}
Men $l''=0$ för alla $l \in L$, så att $(v,l)_{\lambda} = \lambda v
\cdot l$ för alla $v$ och $l$, och villkoret ovan är därför ekvivalent
med
\begin{equation}
  \label{eq:mk}
  P(u) \cdot l = u \cdot l \ \text{för alla $l \in L$}
\end{equation}
vilket uppenbarligen inte beror av $\lambda$. Alltså beror $P(u)$ ej
av $\lambda$, vilket man kanske inte hade väntat sig.

Låt $L^{\perp}$ vara det ortogonala komplementet av $L$ i $W$. Eftersom
$L^{\perp}$ är nollrummet till $P$ i $W$ följer att även $L^{\perp}$ är
$\lambda$-oberoende. Med andra ord har $L$ samma ortogonala komplement
i $W$ oavsett vilken av skalärprodukterna $(u,v)_{\lambda}$ vi använder.

Projektionen av $f$ i $W$ kan förstås bestämmas som summan av
projektionerna i $L$ och i $L^{\perp}$. Beteckna dessa projektioner av
$f$ med $f_L$ och $f_{\perp}$. Av \eqref{eq:mk} följer att $f_L=P(f)$
är den räta linje som i minstakvadratmening bäst approximerar
punkterna $(x_k,y_k)$. $f_L$ kan därför bestämmas med den ``vanliga''
minstakvadratmetoden. Det återstår att bestämma $f_{\perp}$. För att
göra det behöver vi en bas.


\section{En lämplig bas}
\label{sec:bas}

Låt $\phi_k$ vara en funktion vars andraderivata har ett ``tält'' vid
punkten $x_{k+1}$,
\begin{equation*}
  \phi_k''(x) = 
  \begin{cases}
    \frac{x-x_k}{h_k} &\text{för $x_k \leq x \leq x_{k+1}$} \\
    \frac{x_{k+2}-x}{h_{k+1}} &\text{för $x_{k+1} \leq x \leq
      x_{k+2}$} \\
    0 &\text{för övrigt}
  \end{cases}
\end{equation*}
för $k=1,2, \dots n-2$. $\phi_k$:na är uppenbarligen linjärt
oberoende, och givet en funktion i $w \in W$ så finns en linjärkombination
av $\{\phi_k\}$ som har samma andraderivata. Om vi kompletterar med
de två linjära funktionerna $l_1(x)=1$ och $l_2(x) = x$ får vi därför
en bas för $W$, vilket också bevisar att $dim \ W = n$, som utlovat. 

Men $\phi_k$ är inte entydigt bestämd av att andraderivatan är ett
tält; man kan lägga till godtycklig linjär funktion och fortfarande ha
samma andraderivata. Till exempel kan man byta ut $\phi_k$ mot
$\phi_k-P(\phi_k)$, så vi kan förutsätta att $\phi_k \in L^{\perp}$.
Då är $\{\phi_k\}_1^{n-2}$ en bas för $L^{\perp}$.

Nu kan $f_{\perp}$ bestämmas ur
\begin{equation}
  \label{eq:linj1}
  (f_{\perp}, \phi_k)_{\lambda} = (f, \phi_k)_{\lambda} = \lambda f
  \cdot \phi_k \text{ för $k=1,2, \dots n-2$}
\end{equation}

Bilda två symmetriska matriser $A$ och $B$ genom
\begin{align*}
  A_{ij} &= (\phi_i,\phi_j)_0 \\
  B_{ij} &= \phi_i \cdot \phi_j
\end{align*}
så att $A + \lambda B$ är matrisrepresentationen av den bilinjära
formen $(u,v)_\lambda$ på $L^{\perp}$. 

Ansätt $f_{\perp}=\alpha_1 \phi_1 + \dots + \alpha_{n-2} \phi_{n-2}$,
och låt $\beta$ vara vektorn $\beta_i = f \cdot \phi_i$. Då är
\eqref{eq:linj1} ekvivalent med det linjära ekvationssystemet
\begin{equation}
  \label{eq:linj2}
  (A + \lambda B) \alpha = \lambda \beta 
\end{equation}

$A + \lambda B$ och $B$ är och positivt definita, eftersom
$(u,v)_{\lambda}$ och $u \cdot v$ är positivt definita på $W$, och
därmed även på $L^{\perp}$. Även $A$ är positivt definit, vilket man
kan se genom at räkna ut matriselementen. $A$ är tridiagonal, och de
nollskilda elementen är
\begin{equation*}
  \begin{cases}
    A_{k,k} &= \frac13(h_k+h_{k+1}) \\
    A_{k,k+1} = A_{k+1,k} &= \frac16h_{k+1} \\
  \end{cases}
\end{equation*}
$A$ är samma matris som brukar användas för splineinterpolation. Den är
diagonaldominant, och därmed positivt definit.

Alla inblandade matriser är inverterbara, eftersom de är positivt
definita. Vi kan räkna ut
\begin{equation}
  \label{eq:koord}
  \alpha = (A + \lambda B)^{-1} \lambda \beta = (\frac{1}{\lambda} A +
  B)^{-1} \beta
\end{equation}
och den sökta minimerande funktionen $u^*$ blir
\begin{equation*}
  u^*(x) = f_L(x) + \sum_{k=1}^{n-2} \alpha_k \phi_k(x)
\end{equation*}


\section{Parameterberoende}
\label{sec:granser}

Olika värden på $\lambda$ ger olika approximerande kurvor. Stora
$\lambda$ straffar kurvor som avviker från funktionsvärdena $y_k$,
medan små $\lambda$ straffar kurvor med stor krökning. Vad händer i
gränsfallen $\lambda \to 0$ och $\lambda \to \infty$? 

För små $\lambda$ ger \eqref{eq:koord} att
\begin{equation*}
  \alpha = \lambda A^{-1}\beta + \ordo{\lambda^2}
\end{equation*}
Det följer att $u^* \to f_L$ likformigt då $\lambda \to 0$.
%Konvergensen
%är också monoton, och med det menar jag att för varje $x$ och för alla
%tillräckligt små $\lambda$ gäller $u(x) \to f_L(x)$ monotont då
%$\lambda \to 0$. (Hur visa monotonicitet?)

Då $\lambda \to \infty$ gäller, också enligt~\eqref{eq:koord}, att
\begin{equation}
  \label{eq:inf1}
  \alpha = B^{-1} \beta + \frac{1}{\lambda} B^{-1}AB^{-1}\beta +
  \ordo{\frac{1}{\lambda^2}}
\end{equation}
Vad är då $B^{-1} \beta$? Låt $s$ vara den interpolerande
splinefunktionen, vars existens och entydighet följer av
lemma~\ref{l:iso}. Då är $s$ det entydigt bestämda element i $W$ som
minimerar
\begin{equation*}
  \norm{\sigma(u-f)}^2 = \sum_{k=1}^n (u(x_k)-f(x_k))^2
\end{equation*}
av den enkla anledningen att $\sigma(s-f)=0$. Det följer att
\begin{equation}
  \label{eq:inter}
  (s-f) \cdot v = 0 \text{ för alla $v \in W$}
\end{equation}
Genom att först ta $v \in L$ och sedan $v=\phi_k$ ser vi att
\begin{gather}
  P(s) = P(f) = f_L \notag \\
  s \cdot \phi_k = f \cdot \phi_k = \beta_k \text{ för $k=1,2, \dots, n-2$}
  \label{eq:s-proj}
\end{gather}
Vi kan utveckla $s-P(s)$ i basen $\phi_k$, eftersom $s-P(s) \in
L^{\perp}$. Vi får
\begin{equation*}
  s(x) = f_L(x) + \sum_{k=1}^{n-2} \gamma_k \phi_k(x)
\end{equation*}
Nu ger \eqref{eq:s-proj} och definitionen av $B$ att $B \gamma =
\beta$. Men $B$ är inverterbar, så att
\begin{equation*}
  B^{-1}\beta = \gamma
\end{equation*}
Tillsammans med \eqref{eq:inf1} fås nu
\begin{equation}
  \label{inf2}
  \begin{split}
    u^* &= f_L + \sum_{k=1}^{n-2} (\gamma_k + \frac{1}{\lambda}
    (B^{-1}A\gamma)_k) \phi_k + \ordo{\frac{1}{\lambda^2}} \\ 
    &= s + \frac{1}{\lambda} \sum_{k=1}^{n-2} (B^{-1}A\gamma)_k \phi_k
    + \ordo{\frac{1}{\lambda^2}}
  \end{split}
\end{equation}
så att $u^* \to s$ likformigt då $\lambda \to \infty$. Vi har alltså
följande

\begin{result}{Resultat}
  Låt $u_{\lambda}$ vara den funktion som minimerar $J(u)$, för varje
  $\lambda>0$. Låt $l$ vara den räta linje som approximerar punkterna
  $(x_k,y_k)$ i minstakvadratmening, och låt $s$ vara den kubiska
  spline, med naturliga randvillkor, som interpolerar samma
  punkter. Då gäller
  \begin{itemize}
  \item $u_{\lambda}(x) \to l(x)$ likformigt då $\lambda \to 0$
  \item $u_{\lambda}(x) \to s(x)$ likformigt då $\lambda \to \infty$
  \end{itemize}
\end{result}
\end{document}
