NumMod 1 pset 1

1. Feladat

Gondoljuk meg, hogy

$$\underset{x\ne 0}{\sup }\frac{\Vert Ax{\Vert }^{\prime \prime }}{\Vert x{\Vert }^{\prime }}=\underset{\Vert x{\Vert }^{\prime }=1}{\sup }\Vert Ax{\Vert }^{\prime \prime }=\underset{\Vert x{\Vert }^{\prime }\le 1}{\sup }\Vert Ax{\Vert }^{\prime \prime }.$$

Sol.:

$$\underset{x\ne 0}{\sup }\frac{||Ax|{|}^{\prime \prime }}{||x|{|}^{\prime }}=\underset{x\ne 0}{\sup }{\left|\left|A\frac{x}{||x|{|}^{\prime }}\right|\right|}^{\prime \prime }=\underset{x=1}{\sup }||Ax|{|}^{\prime \prime }=\underset{x\le 1}{\sup }||Ax||$$

2. Feladat

Legyen $(V,\Vert {\Vert }^{\prime })$ normált tér. Jelöljük $\Vert \Vert$-vel az $L(V,V)$ téren indukált operátornormát. Mutassuk meg, hogy ez utóbbi szubmultiplikatív, azaz $A,B\in L(V,V)$ esetén

$$\Vert AB\Vert \le \Vert A\Vert \Vert B\Vert .$$

Sol.:

$$||AB||=\underset{||x||=1}{\sup }||ABx||\le \underset{||x||=1}{\sup }||A||\cdot ||Bx||\le ||A||\cdot ||B||$$

Mert: $||Ax||\le ||A||\cdot ||x||$

3. Feladat

Legyen $(V,\Vert \Vert )$ normált tér. Az eddigiek felhasználásával definiáljunk egy $\Vert {\Vert }_{\ast }$ leképezést, amivel $(V^{\ast },\Vert {\Vert }_{\ast })$ is normált tér.

Sol.:

$$||v^{\ast }|{|}_{\ast }=\underset{||x||=1}{\sup }|v^{\ast }\cdot x|$$ $$v^{\ast }\in {\mathbb{R}}^n⟹v^{\ast }\cdot x\in \mathbb{R}$$

4. Feladat

Duális norma

A $\Vert {\Vert }_{\ast }$ leképezést szokás a $\Vert \Vert$ duális normájának hívni.

Mutassuk meg, hogy a $\Vert {\Vert }_2$ duális normája önmaga.

Sol.:

$$\text{Kell: }||\cdot |{|}_2\text{ dualisa }||\cdot |{|}_2$$

Definiciobol:

$$||x^{\ast }|{|}_2:=\underset{||v|{|}_2=1}{\sup }|x^{\ast }\cdot v|=?||x^{\ast }|{|}_2$$

Cauchy Schwartz:

$$|x^{\ast }\cdot v|\le ||x^{\ast }|{|}_2\cdot ||v|{|}_2\le ||x^{\ast }|{|}_2$$

Mert $||v|{|}_2=1$.

Tehat felulrol korlatoztuk, most be kene latni hogy el is tudjuk erni ezt a korlatot.

All.: $v:=\frac{x}{||x|{|}_2}$ -et valasztva el is erheto. Ekkor:

$$x^{\ast }\cdot v=\frac{x^{\ast }x}{||x|{|}_2}=\frac{||x|{|}_2^2}{||x|{|}_2}=||x|{|}_2$$

5. Feladat

Mutassuk meg, hogy $\Vert {\Vert }_1$ és $\Vert {\Vert }_{\infty }$ egymás duális normái.

Sol.:

Holder egyenlotlenseggel megoldhato (gyakon nem volt).

Rayleigh-hányados

Legyen az $A$ mátrix önadjungált $(A^{\ast }=A)$. Ekkor a sajátértékei valósak (miért?). Egy $x\ne 0$ vektor esetén a

$$R_A(x)=\frac{x^{\ast }Ax}{x^{\ast }x}$$

kifejezést Rayleigh-hányadosnak nevezzük.

6. Feladat

Mutassuk meg, hogy ha $A$ önadjungált, akkor tetszőleges $x\ne 0$ vektorra

$${\lambda }_{\min }(A)\le R_A(x)\le {\lambda }_{\max }(A).$$

Sol.:

$$||A|{|}_2^2=\underset{||x|{|}_2=1}{\sup }||Ax|{|}_2^2=\underset{||x|{|}_2=1}{\sup }{x}^{\ast }{A}^{\ast }Ax=\underset{x\ne 0}{\sup }\frac{x^{\ast }{A}^{\ast }Ax}{x^{\ast }x}=\underset{x\ne 0}{\sup }{R}_{A^{\ast }A}(x)$$

Mivel $A\in {\mathbb{C}}^{n\times m}$ onadajungalt, tehat $A^{\ast }=A$
$A=S{\Lambda }_n{S}^{-1}=Q\Delta Q^{\ast }$ a diagonalizacioja, ahol $Q{Q}^{\ast }=I$.

$$R_A(x)=\frac{x^{\ast }(Q\Lambda Q^{\ast })x}{x^{\ast }x}=\frac{(x^{\ast }Q)\Lambda (Q^{\ast }x)}{x^{\ast }x}=$$ $$(y:=Q^{\ast }x)$$ $$=\frac{y^{\ast }\Lambda y}{y^{\ast }{Q}^{\ast }Qy}=\frac{y^{\ast }\Lambda y}{y^{\ast }y}=R_{\Lambda }(y)=R_{\Lambda }(Q^{\ast }x)$$

tfh $||y||=1$, ekkor:

$$R_{\Lambda }(Q^{\ast }y)=y^{\ast }\Lambda y=y^{\ast }\left[\begin{array}{ccccccc}{\lambda }_1& & \dots & & \dots & & 0\\ 0& & {\lambda }_2& & \dots & & 0\\ ⋮& & ⋮& & ⋮& & ⋮\\ 0& & \dots & & \dots & & {\lambda }_n\end{array}\right]y={\lambda }_1{\bar{y}}_{1}y+\cdots +{\lambda }_n{\bar{y}}_n{y}_n\le {\lambda }_{\max }$$

Továbbá, $R_{\Lambda }(Q^{\ast }y)\ge {\lambda }_{\min }$.

Tehát ${\lambda }_{\min }(A)\le R_A(x)\le {\lambda }_{\max }(A)$

8. Feladat

Mutassuk meg, hogy a kettes vektornorma által indukált mátrixnorma invariáns unitér mátrixszal való szorzásra, azaz: ha $U,V$ unitér mátrixok $(U^{\ast }U=I=U{U}^{\ast })$, akkor
$\Vert VAU{\Vert }_{2,2}={\sup }_{||x|{|}_2=1}||VAUx|{|}_2=\Vert A{\Vert }_{2,2}.$

Sol.:

Eloszor lassuk be hogy $||Ux||=||x||$ igaz, mert

$$||Ux|{|}^2=(Ux{)}^{\ast }(Ux)=x^{\ast }{U}^{\ast }Ux=x^{\ast }(U^{\ast }U)x=x^{\ast }Ix=x^{\ast }x=||x|{|}^2$$

Tehat valoban $||Ux||=||x||$.

Tovabba:

$$\underset{||x|{|}_2=1}{\sup }||VAUx|{|}_2=\underset{||x|{|}_2=1}{\sup }||AUx|{|}_2=\underset{||Ux||=||x||=||y||=1}{\sup }||Ay|{|}_2=||A|{|}_2$$

9. Feladat

Tegyük fel, hogy $A=U\Sigma V^{\ast }$ alakba írható, ahol $U,V$ unitér mátrixok, $\Sigma$ pedig diagonális mátrix, ${\sigma }_1\ge {\sigma }_2\ge \dots \ge {\sigma }_n\ge 0$ főátlóbeli elemekkel.

Mutassuk meg, hogy ekkor

$$\Vert A{\Vert }_{2,2}={\sigma }_1,$$

továbbá, amennyiben ${\sigma }_n>0$, akkor $A$ invertálható és

$$\Vert A^{-1}{\Vert }_{2,2}={\sigma }_n^{-1}.$$

Sol.:

Kondíciószám

Ha az $A$ mátrix invertálható, akkor adott $\Vert \Vert$ indukált norma szerinti kondíciószáma alatt az
$\Vert A\Vert \Vert A^{-1}\Vert$ kifejezést értjük. Ennek motiválásához legyen $Ax=b,Ay=c$. Ekkor

$$\Vert b\Vert \Vert x-y\Vert =\Vert Ax\Vert \Vert A^{-1}(b-c)\Vert \le \Vert A\Vert \Vert x\Vert \Vert A^{-1}\Vert \Vert b-c\Vert =\Vert x\Vert \Vert b-c\Vert {\mathrm{cond}}_{\Vert \Vert }(A).$$

Ha $x\ne 0$, akkor $b\ne 0$. Ekkor normáikkal átosztva adódik, hogy

$$\frac{\Vert x-y\Vert }{\Vert x\Vert }\le \frac{\Vert b-c\Vert }{\Vert b\Vert }{\mathrm{cond}}_{\Vert \Vert }(A).$$

Egy következmény, hogy ha egy $Ax=b$ egyenletrendszer jobboldala nem pontosan (például mérési hibákkal terhelten) áll rendelkezésünkre, akkor az így kapott hibás $Ay=c$ rendszer $y$ megoldásának relatív hibája az adott $\Vert \cdot \Vert$ norma szerint az eredeti rendszer $x$ megoldásához képest legfeljebb az $A$ mátrixtól és az alkalmazott normától függõ konstansszorosa lehet a $c$ vektor $b$-hez képest vett relatív hibájának.

10. Feladat

Tegyük fel, hogy $A$ önadjungált.

a) Adjunk egy egyszerű formulát az $\Vert A{\Vert }_{2,2}$ kifejezésre.
Tudjuk, hogy a kettes norma altal indukalt matrixnormara: $\Vert A{\Vert }_{2,2}=\sqrt{{\lambda }_{\max }(A^{\ast }A)}$
Mivel $A$ ondajungalt, ezert $A=A^{\ast }$, tehat $||A|{|}_{2,2}=\sqrt{{\lambda }_{\max }(A^2)}$.

b) Tegyük fel, hogy $A$ invertálható is. Adjunk egy egyszerű formulát az $\Vert A^{-1}{\Vert }_{2,2}$ kifejezésre.
Szinten mivel $A$ ondajungalt, ezert $A=A^{\ast }$, tehat $I=A^{-1}{A}^{\ast }$ es $(A^{\ast }{)}^{-1}=A^{-1}$.
Ekkor $||A^{-1}|{|}_{2,2}=\sqrt{{\lambda }_{\max }(A^{-1}(A^{-1}{)}^{\ast })}=\sqrt{{\lambda }_{\max }(A^{-1}{A}^{-1})}$.

11. Feladat

Gondoljuk meg, hogy ez a két formula az $1$-es és $\infty$-normák esetén az $(1,n)$ méretű mátrixokon, azaz sorvektorokon, a várt, $\infty$-es és $1$-es normákat adják vissza.

12. Feladat

Legyen $u,v$ két vektor. Mik a sajátértékei és sajátvektorai az $u{v}^{\ast }$ mátrixnak?

17. Feladat

Mutassuk meg, hogy ${\mathrm{cond}}_{\Vert \cdot \Vert }\ge 1.$

Sol.:

$${\mathrm{cond}}_{\Vert \cdot \Vert }=||A||\cdot ||A^{-1}||\ge ||A\cdot A^{-1}||=||I||=1$$

18. Feladat

Legyen $U$ unitér mátrix. Mennyi ${\mathrm{cond}}_2(U)$?

Sol.:

$${\mathrm{cond}}_2(U)=||U|{|}_2\cdot ||U^{-1}|{|}_2=||U||\cdot ||U^{\ast }||=1\cdot 1=1$$

19. Feladat

Legyen $A=U\Sigma V^{\ast }$, ahol $U,V$ unitér és $\Sigma$ diagonális mátrix ${\sigma }_1\ge {\sigma }_2\ge \dots \ge {\sigma }_n>0$ főátlóbeli elemekkel. Adjunk egy egyszerű formulát a
${\mathrm{cond}}_2(A)$ mennyiségre.

Sol.:

(9. feladatra epit)

25. Feladat

Írjunk programot az

A_n = \left(\matrix{2 & -1 & 0 & \dots & 0\cr -1 & 2 & -1 & \dots & 0 \cr 0 & -1 & 2 & \dots & 0 \cr \vdots & \ddots & \ddots & \ddots& \vdots \cr 0 & \dots & 0 & -1 & 2}\right)

és a

H_n = \left(\matrix{1 & 1/2 & 1/3 & \dots & 1/n \cr 1/2 & 1/3 & 1/4 & \dots & 1/(n+1) \cr 1/3 & 1/4 & 1/5 & \dots & 1/(n+2) \cr \vdots & \vdots & \vdots & \vdots& \vdots \cr 1/n & 1/(n+1) & 1/(n+2) & \dots & 1/(2n-1)}\right)

mátrixok megkonstruálására, majd számíttassuk is ki ezek 1-es, illetve 2-es norma szerinti kondíciószámát egy megfelelő parancs segítségével.

related: NumMod 1