Review Gram-Schmidt orthogonalization and orthogonal complement

Page 1

Review

Gram-Schmidt orthogonalization and orthogonal complement

⌅⌅ Theorem 6.3: V is an inner product space; S = {v1, · · · , vk} ✓ V is orthogonal. Then

y = P_k

i=1 a_iv_i ) aj = ^hy,vji

kvjk², j = 1, · · · , k.

⌅⌅ Corollary 6.3.1: If S is orthonormal, y = P_k

i=1 a_iv_i ) ai = hy, vii ) y = P_k

i=1hy, viivi.

⌅⌅ Corollary 6.3.2: Orthogonality implies linear independence.

Page 2

⌅⌅ Gram-Schmidt orthogonalization:

v₁ = w₁

v₂ = w₂ ^hw2,v1i

kv1k² v₁ v₃ = w₃ ^hw3,v1i

kv1k² v₁ ^hw3,v2i

kv2k² v₂

· · ·

⌅⌅ Theorem 6.4: V is an inner product space; S = {w1, · · · , wⁿ} ✓ V is linearly independent. Then letting v₁ = w₁ and v_i = w_i P_{i 1}

j=1

hwi,v_ji

kvjk² v_j, i = 2, · · · , n,

makes S⁰ = {v1, · · · , vⁿ} orthogonal and span(S⁰) = span(S).

Page 3

⌅⌅ Theorem 6.5: V is an inner product space; dim(V ) < 1. Then 1. V has an orthonormal basis = {v1, · · · , vⁿ}.

2. 8x 2 V, x = P_n

i=1hx, viivi

⌅ That is, [x] = (hx, v1i, · · · , hx, vⁿi)^t.

⌅ 2 is called a Fourier series expansion.

⌅ hx, vii are called Fourier coefficients.

⌅ kxk² = hP_n

i=1hx, viivi, P_n

j=1hx, vjivji

= P_n

i=1 P_n

j=1hx, viihx, vjihvi, v_ji = P_n

i=1 |hx, vii|² : Parseval’s relation

⌅ example: C([0, 2⇡), C) with hf, gi = _2⇡¹ R _2⇡

0 f (t)g(t)dt

= {fk(t) = e^ikt : k 2 Z} is an orthonormal basis.

hf, f_ki = _2⇡¹ R _2⇡

0 f (t)e ^iktdt : k-th Fourier coefficient of f

Page 4

⌅⌅ Corollary 6.5: V is an inner product space; dim(V ) < 1;

= {v1, · · · , vⁿ} is an orthonormal basis for V ; T is a linear operator on V ; A = [T ] . Then A_ij = hT (vj), v_ii.

⌅⌅ orthogonal complement S^? of S : S^? = {x 2 V : hx, yi = 0, 8y 2 S}

⌅ Do not confuse this with the set complement

⌅ S^? is a subspace for any set S.

⌅ S ✓ (S^?)^?, but if S is a subspace, then S = (S^?)^?.

⌅ {0}^? = V, V ^? = {0}

⌅ [End of Review]

Page 5

⌅⌅ Theorem 6.6. and Corollary 6.6: V is an inner product space; W is a subspace; dim(W ) < 1; {v1, · · · , v_k} is an orthonormal basis for W ;y 2 V. Then

1. y = u + z, where u 2 W is unique and closest to y, and if dim(V ) < 1,

z 2 W^? is unique and closest to y.

2. u = P_k

i=1hy, viivi.

⌅ proof:

Let u = P_k

i=1hy, viivi. and z = y u.

) u 2 W

To show z 2 W^?, we only need to show hz, vii = 0, j = 1, · · · , k.

•

① ②

③

爬河

①

③

Page 6

hz, vji = h(y P_k

i=1hy, viivi), v_ji

= hy, vji hP_k

i=1hy, viivi, v_ji = hy, vji P_k

i=1hy, viihvi, v_ji

= 0 [hvi, v_ji = ij] ) z 2 W^?

“unique”: Let y = u⁰ + z⁰, u⁰ 2 W, z⁰ 2 W^?.

) u u⁰ = z⁰ z, u u⁰ 2 W, z⁰ z 2 W^? [y = u + z]

) u u⁰ = z⁰ z 2 W \ W^? = {0}

) u⁰ = u and z⁰ = z

“closest”: For any x in W,

ky xk² = k(y u) + (u x)k²

= h(y u) + (u x), (y u) + (u x)i

= ky uk²+ku xk²+hy u, u xi+hu x, y ui iii. _utz

Page 7

) ky xk² = ky uk² + ku xk² [y u 2 W ^?, u x 2 W ]

) ky xk² ky uk²

A similar proof can show that z is unique and closest to y.

⌅⌅ orthogonal projection of y on W : P_W^?(y) = P_k

i=1hy, viivi, where {v1, · · · , vk} is an orthonormal basis for W .

⌅ A non-orthogonal projection is shown above. V = W₁ W₂

⌅⌅ example: Consider the inner product space PR _{1 2}(R) withhf, gi =

1 f (x)g(x)dx.

We found earlier the orthonormal basis by G-S process.

= {v1, v₂, v₃} = ⇢q

12,

q3 2x,

q5

8(3x² 1) .

U-U ^{t Z}

t.y-uc.it#ft

<肅w

<Ut ^Z _, ^{Ni >}

=

= <a _, ^vi>

Page 8

Let f(x) = a + bx + cx². hf, v1i = R ₁

1(a + bx + cx²) q1

2dx =

p2

3 (3a + c) hf, v2i = R ₁

1(a + bx + cx²) q3

2xdx =

q2 3b hf, v3i = R ₁

1(a + bx + cx²) q5

8(3x² 1)dx = ²₃ q2

5c f (x) = hf, v1iv1 + hf, v2iv2 + hf, v3iv3

=

p2

3 (3a+c)· q1

2+ q2

3b· q3

2x+²₃ q2

5c· q5

8(3x² 1)) = a+bx+cx² Let W = span({v1, v₃}) =span

✓⇢q1 2,

q5

8(3x² 1)

◆

=span({1, x²}) P_W^?(f ) = hf, v1iv1 + hf, v3iv3

=

p2

3 (3a + c) ·

q1

2 + ²₃ q2

5c ·

q5

8(3x² 1) = a + cx² P ^?

W^?(f ) = hf, v2iv2 = bx

Page 9

If instead we let W =^⇠ span({v1, v₂}) =span✓⇢q

12, q3

2x

◆

=span({1, x}) P ^?_⇠

W(f ) = hf, v1iv1 + hf, v2iv2 = (a + ^c₃) + bx P ^?_⇠

W^?

(f ) = hf, v3iv3 = c(x^{2 1}₃)

So (a + ^c₃) + bx is the polynomial in W^⇠ that is “closest” to f, and c(x^{2 1}₃) is the polynomial in W^{⇠ ?} that is “closest” to f.

Note that span({1, x}) and span({x²}) are not orthogonal comple- ments of each other, while span({(1, 0, 0), (0, 1, 0)}) and span({0, 0, 1}) are . Why?

遼閑

Page 10

⌅⌅ Theorem 6.7: V is an inner product space; dim(V ) = n; S = {v1, · · · , v_k} is an orthonormal set. Then

1. S can be extended to an orthonormal basis {v1, · · · , v_k, v_k+1, · · · , vⁿ} for V .

2. W = span(S) ) {v_k+1, · · · , vn} is a basis for W^?.

3. For any subspace W of V , dim(V ) = dim(W )+ dim(W^?).

⌅ proof of 2: 8x 2 W^?, x = P_n

i=1 a_iv_i [basis for V ]

) hx, vii = ai = 0, i = 1, · · · , k [orthogonal complement]

) x = P_n

i=k+1 a_iv_i ^{↳ View}

Page 11

Adjoint

⌅⌅ The adjoint T^⇤ of a linear operator T on a finite-dimensional inner product space V is another operator on V such that for any x and y in V, hT (x), yi = hx, T^⇤(y)i.

⌅ On Fⁿ, this correspond to the conjugate transpose A^⇤ = A^t of the matrix A. A^⇤ is called the adjoint of A.

hx, yi = P_n

i=1 x_iy_i = y^tx = y^⇤x

hAx, yi = y^⇤(Ax) = (A^⇤y)^⇤x = hx, A^⇤yi That is, (L_A)^⇤ = L_A⇤.

⌅ In R², if T is rotation by ✓, then T ^⇤ = T ¹ is rotation by ✓;

and if T is projection onto x axis, then T^⇤ = T.

✓cos sin sin cos

◆

: rotation by

( _con

jugatetranspc.se

Existence of H ⁼ ?

로 Unique

岾金 ^풣

軀批 ^任閭門

.fr?Eaib).TLN=(a.o ^③

西停

印作偕 믻 햛 炸漑

T.

一一

Page 12

⌅⌅ For the derivation of adjoint, consider a scalar-valued linear trans- formation g : V ! F, which is also called a functional.

⌅⌅ Theorem 6.8: V is an inner product space; dim(V ) < 1; g : V ! F is a linear transformation. Then 9y, unique in V, such that 8x 2 V, g(x) = hx, yi.

proof: Let = {v1, · · · , vⁿ} be an orthonormal basis for V, and, for the given g, let y = P_n

i=1 g(v_i)v_i. Then 8x 2 V, g(x) = g(P_n

i=1hx, viivi) [orthonormal basis]

= P_n

i=1hx, viig(vi) [linear]

= P_n

i=1hx, g(vi)v_ii = hx, P_n

i=1 g(v_i)v_ii = hx, yi

“uniqueness” : 8x 2 V, g(x) = hx, yi = hx, y⁰i ) y = y⁰ [Thm 6.1-5]

⌅ Note that this y is not affected by the choice of the basis.

f ^e

ftp.y.me#iF=gt

Page 13

⌅⌅ example: g : R³ ! R such that g((a1, a₂, a₃)) = 2a₁ a₂ + 4a₃. y = P_n

i=1 g(v_i)v_i = g(e₁)e₁ + g(e₂)e₂ + g(e₃)e₃ = (2, 1, 4) g((a₁, a₂, a₃)) = h(a1, a₂, a₃), (2, 1, 4)i = 2a1 a₂ + 4a₃

⌅⌅ Theorem 6.9: V is an inner product space; dim(V ) < 1; T is a linear operator on V. Then 9T^⇤, a unique operator on V, such that

1. 8x, y 2 V, hT (x), yi = hx, T^⇤(y)i.

2. T^⇤ is linear.

⌅ proof: Fix y and let g(x) = hT (x), yi.

) g is linear. [T is linear; h·, yi is linear.]

) 8x 2 V, g(x) = hx, y⁰i for some y⁰, which is unique in V. [Thm 6.8]

Define T^⇤ such that T^⇤(y) = y⁰.

) hT (x), yi = hx, y⁰i = hx, T^⇤(y)i :“1”

• ( ? ^{. 00) ( 0-10) (004})^{= -}

EU

사가 어떤것인지는

정의인참1TH성

→ Property^{는 나중에 만 )}

Page 14

“linearity”: 8x 2 V,

hx, T^⇤(c₁y₁ + c₂y₂)i = hT (x), c1y₁ + c₂y₂i [1]

= c₁hT (x), y1i + c2hT (x), y2i

= c₁hx, T^⇤(y₁)i + c2hx, T^⇤(y₂)i [1]

= hx, c1T^⇤(y₁) + c₂T ^⇤(y₂)i

) T^⇤(c₁y₁ + c₂y₂) = c₁T^⇤(y₁) + c₂T ^⇤(y₂) [Thm 6.1-5]

⌅⌅ Theorem 6.10: V is an inner product space; dim(V ) < 1;

= {v1, · · · , vⁿ} is an orthonormal basis for V ; T is a linear operator on V .

Then [T ^⇤] = [T ]^⇤.

proof: Let A = [T ] and B = [T ^⇤] . ) Bij = hT^⇤(v_j), v_ii [Corol 6.5]

= hvi, T^⇤(v_j)i = hT (vi), v_ji = Aji = (A^⇤)_ij

⇒

Page 1

Review

⌅⌅ Theorem 6.6. and Corollary 6.6: V is an inner product space; W is a subspace; dim(W ) < 1; {v1, · · · , vk} is an orthonormal basis for W ;y 2 V. Then

1. y = u + z, where u 2 W is unique and closest to y, and if dim(V ) < 1, z 2 W^? is unique and closest to y.

2. u = P_k

i=1hy, viivi.

⌅⌅ orthogonal projection of y on W : P_W^?(y) = P_k

i=1hy, viivi, where {v1, · · · , vk} is an orthonormal basis for W .

Page 2

⌅⌅ Theorem 6.7: V is an inner product space; dim(V ) = n; S = {v1, · · · , v_k} is an orthonormal set. Then

1. S can be extended to an orthonormal basis {v1, · · · , vk, v_k+1, · · · , vⁿ} for V .

2. W = span(S) ) {v_k+1, · · · , vⁿ} is a basis for W^?.

3. For any subspace W of V , dim(V ) = dim(W )+ dim(W^?).

⌅⌅ The adjoint T^⇤ of a linear operator T on a finite-dimensional inner product space V is another operator on V such that for any x and y in V, hT (x), yi = hx, T^⇤(y)i.

⌅ On F ⁿ, this correspond to the conjugate transpose A^⇤ = A^t of the matrix A. A^⇤ is called the adjoint of A.

hAx, yi = y^⇤(Ax) = (A^⇤y)^⇤x = hx, A^⇤yi. That is, (LA)^⇤ = L_A⇤.

forthogondcomplimeuT.tw

王石比_{) (}ATF⁽ _Y) = LH Dy⁾

Page 3

⌅⌅ Theorem 6.8: V is an inner product space; dim(V ) < 1; g : V ! F is a linear transformation (functional). Then 9y, unique in V, such that 8x 2 V, g(x) = hx, yi, where y = P_n

i=1 g(v_i)v_i.

⌅⌅ example: g : R³ ! R such that g((a1, a₂, a₃)) = 2a₁ a₂ + 4a₃. y = P_n

i=1 g(v_i)v_i = g(e₁)e₁ + g(e₂)e₂ + g(e₃)e₃ = (2, 1, 4)

⌅⌅ Theorem 6.9: V is an inner product space; dim(V ) < 1; T is a linear operator on V. Then 9T^⇤, a unique operator on V, such that

1. 8x, y 2 V, hT (x), yi = hx, T^⇤(y)i.

2. T^⇤ is linear.

⌅⌅ Theorem 6.10: V is an inner product space; dim(V ) < 1;

= {v1, · · · , vⁿ} is an orthonormal basis for V ; T is a linear operator on V . Then [T ^⇤] = [T ]^⇤.

⌅⌅ [End of Review]

Page 4

⌅⌅ Corollary 6.10: A is an n ⇥ n matrix. Then LA^⇤ = (L_A)^⇤. proof: Let be the standard basis for F ⁿ.

[(L_A)^⇤] = [L_A]^⇤ [Thm 6.10] = A^⇤ = [L_A⇤] .

Then the uniqueness of the representation completes the proof.

⌅ This can directly be shown by taking conjugate transpose of the matrix.

hLA(x), yi = hAx, yi = y^⇤(Ax)

= (A^⇤y)^⇤x = hx, A^⇤yi = hx, LA^⇤(y)i ! (LA)^⇤ = L_A⇤.

⌅⌅ example: T : C³ ! C³; is the standard basis.

T (a, b, c) = (2a + ib, b 5ic, a + (1 i)b + 3c) [T ] =

0

@2 i 0

0 1 5i

1 1 i 3

1

A , [T^⇤] = [T ]^⇤ = 0

@ 2 0 1

i 1 1 + i 0 5i 3

1 A T ^⇤(a, b, c) = (2a + c, ia + b + (1 + i)c, 5ib + 3c)

=A

<^자_, KA

片姓

i.

.

邨

Page 5

⌅⌅ example: Consider the inner product space PR _{1 2}(R) with hf, gi =

1 f (x)g(x)dx.

Let f(x) = a + bx + cx² and g(x) = p + qx + rx².

When T (f) = f⁰ = b + 2cx, what would T^⇤(g) look like?

=

⇢q1 2,

q3 2x,

q5

8(3x² 1) [orthonormal basis]

[g] = ⇣p

2p +

p2 3 r,

p6

3 q, ²

p10

15 r⌘_t [T ] =

0

@0p

3 0 0 0 p

15 0 0 0

1

A , [T^⇤] = [T ]^⇤ = 0

@

0 0 0

p3 0 0 0 p

15 0 1 A

[T^⇤(g)] = [T^⇤] [g]

< 9시^{, 닥 > =? ⇒} g쌰 룱 ^{미is > 닺}

.io

器漣

漲拓

Page 6

[T^⇤(g)] = 0

@

0 0 0

p3 0 0 0 p

15 0 1 A

0 BB

@

p2p +

p2 3 r

p6 3 q

2p 1510r

1 CC A =

0 BB

@ p 0

6(p + ^r₃) p10q

1 CC A

T ^⇤(p + qx + rx²) =p

6(p + ^r₃) q3

2x +p 10q

q5

8(3x² 1)

= ⁵₂q + (3p + r)x + ¹⁵₂ qx² We can confirm this result by computing hT (f), gi = R ₁

1(b + 2cx)(p + qx + rx²)dx = 2bp + ²₃br + ⁴₃cq

= R ₁

1(a + bx + cx²)( ⁵₂q + (3p + r)x + ¹⁵₂ qx²)dx = hf, T^⇤(g)i.⁼

Page 8

⌅⌅ Theorem 6.11 and Corollary 6.11: V is an inner product space; T and U are linear operators on V ; A and B are n ⇥ n matrices; c is a scalar. Then the following hold.

(a) (T + U)^⇤ = T^⇤ + U^⇤ (A + B)^⇤ = A^⇤ + B^⇤ (b) (cT )^⇤ = cT^⇤ (cA)^⇤ = cA^⇤

(c) (T U )^⇤ = U^⇤T^⇤ (AB)^⇤ = B^⇤A^⇤ (d) (T^⇤)^⇤ = T (A^⇤)^⇤ = A (e) I^⇤ = I I_n^⇤ = I_n

proof of (c): 8x, y 2 V,

hx, (T U)^⇤(y)i = h(T U)(x), yi = hT (U(x)), yi

= hU(x), T^⇤(y)i = hx, U^⇤(T^⇤(y))i

= hx, (U^⇤T^⇤)(y)i.

L_(AB)⇤ = (L_AB)^⇤ = (L_AL_B)^⇤ [Corol 6.10, Thm 2.15-6]

= (L_B)^⇤(L_A)^⇤ = L_B⇤L_A⇤ = L_B⇤A^⇤

Page 9

proof of (d):

hT (x), yi = hx, T^⇤(y)i = hT^⇤(y), xi = hy, (T ^⇤)^⇤(x)i

= h(T^⇤)^⇤(x), yi ) (T^⇤)^⇤ = T

⌅⌅ least square approximation:

measurements: (t₁, y₁), (t₂, y₂), · · · , (t^m, y_m)

approximation: Find a and b such that y = at + b, or

find a, b and c such that y = at² + bt + c.

criterion: Minimize E = P_m

i=1[y_i (at_i + b)]², or E = P_m

i=1[y_i (at²_i + bt_i + c)]².

( No exit Solution _, East ^error)

fcarrefit.mg

_recession

Page 10

) E = ky Axk², where y = (y₁, · · · , y^m)^t, and A =

0

@ t₁ 1 ... ...

t_m 1 1

A , x =

✓a b

◆

, or A = 0

@ t²₁ t₁ 1 ... ... ...

t²_m t_m 1 1

A , x = 0

@a b c

1 A

) Find x that minimizes ky Axk².

Terror

a.b.ctamtcti.my

"

~ ^{Eth element}atitboratitbtn.to

= 통 ^{Mi - (}ADD2

Page 11

⌅⌅ orthogonality principle:

The minimizing x₀ satisfies 8x, hAx, y Ax₀i = 0

W = R(L_A)

= {Ax : x 2 Fⁿ}

= {P

a_ix_i : x 2 Fⁿ}

where a_i are the column vectors of A.

So W is the column space of A.

The principle is quite general.

⌅⌅ Lemma 6.12.1: A 2 M^m_⇥n(F ); x 2 Fⁿ; and y 2 F^m. Then hAx, yim = hx, A^⇤yin.

proof: hAx, yim = y^⇤(Ax) = (y^⇤A)x = (A^⇤y)^⇤x = hx, A^⇤yiⁿ

⌅⌅ Lemma 6.12.2: A 2 M^m_⇥n(F ). Then rank(A^⇤A) = rank(A).

m) ^{# 아}

Di

Y

otparanln.IE

No Solution

Since M7개 ^{→ (}불능)

ERm

구최소로하는 ^Xo

찾는일

= R^"

nxm.mx ^{n = nxn}

Page 12

proof: (Ax = 0 ) A^⇤Ax = 0) ) N(LA) ✓ N(LA^⇤A)

) nullity(LA)  nullity(LA^⇤A)

) rank(LA^⇤A)  rank(LA) [dim thm: nullity + rank = n]

) rank(A^⇤A)  rank(A) [also from Thm 3.7]

So we need only to show that N(L_A⇤A) ✓ N(LA).

x 2 N(LA^⇤A) ) A^⇤Ax = 0

) hA^⇤Ax, xiⁿ = hAx, Axi^m = 0 ) Ax = 0 ) x 2 N(LA)

Page 13

⌅⌅ Theorem 6.12: A 2 Mm⇥n(F ); y 2 F^m. Then 9x0 2 Fⁿ such that 1. A^⇤Ax₀ = A^⇤y

2. 8x 2 Fⁿ, kAx0 yk  kAx yk 3. rank(A) = n ) x0 = (A^⇤A) ¹A^⇤y.

⌅ proof: Let W = {Ax : x 2 Fⁿ} = R(LA) [col sp of A]

) y = u + z, u 2 W, z 2 W^? such that u 2 W is unique and closest to y, and

z 2 W ^? is unique and closest to y. [Thm 6.6]

) 9x0 such that u = Ax₀. : “2”

) z = y Ax₀ 2 W ^? ) 8x 2 Fⁿ, hAx, y Ax₀i = 0 ) 8x 2 Fⁿ, hx, A^⇤(y Ax₀)i = 0 : “1”, orthogonality

“3” follows from Lemma 6.12.2 and “1”.

⌅⌅ Corollary 6.12: A 2 Mm⇥n(F ); rank(A) = n. Then A^⇤A is invert- ible.

( East Square ^Solution)

= 0