CS计算机代考程序代写 matlab Linear Least Squares

Linear Least Squares
CS/SE 4X03
Ned Nedialkov McMaster University March 4, 2021

Outline
Example: linear least squares fit Solving overdetermined systems Normal equations

Example: linear least squares fit Solving overdetermined systems Normal equations Example: linear least squares fit
• Assume a program runs in αnβ, where α and β are real constants we don’t know
• How to determine them?
• Run the program with sizes n1, n2, . . . , nm and measure the
corresponding CPU times t1, t2, . . . , tm, m > 2
• Write αnβi = ti, i = 1,…,m
• Then
lnα+βlnni =lnti, i=1,…,m
• Letx=lnα
• Then
1·x+lnni·β=lnti, i=1,…,m
Copyright © 2021 N. Nedialkov. All rights reserved. 3/9

Example: linear least squares fit
Solving overdetermined systems Normal equations
• Write
• Then
1 · x + ln n1 · β = ln t1 1 · x + ln n2 · β = ln t2
.
1 · x + ln nm · β = ln tm
1 lnn1
1 lnn2 􏰆x􏰇
lnt1
lnt2 
=  .  = b
Ay = . . 
. .β .
1 lnnm lntm • Solve in Matlab as y = A\b
Copyright © 2021 N. Nedialkov. All rights reserved.
4/9

Example: linear least squares fit Solving overdetermined systems Normal equations
• y(1)=lnα, α=exp(y(1))
• β = y(2)
• Find these constants when solving linear systems using Matlab’s \
Copyright © 2021 N. Nedialkov. All rights reserved. 5/9

Example: linear least squares fit Solving overdetermined systems Normal equations Solving overdetermined systems
• A∈Rm×n,b∈Rm m>n
• Ax = b is an overdetermined system: more equations than variables
• Find x that minimizes ∥b − Ax∥2
• r = b − Ax
•∥r∥2=􏰃m r2=􏰃m 􏰋b−􏰃n a x􏰌2
• Let
2
i=1 i i=1 i j=1 ij j
1 1m n 2
φ(x)= ∥r∥2= 􏰄 bi−􏰄aijxj 22
i=1 j=1
Copyright © 2021 N. Nedialkov. All rights reserved. 6/9

Example: linear least squares fit Solving overdetermined systems Normal equations • We want to find the minimum of φ(x)
• Necessary conditions are
∂φ = 0, for k = 1,…,n
∂xk
mn 2
0=∂φ= ∂ 1􏰄 bi−􏰄aijxj
∂xk
∂xk 2    i=1 j=1
m  n 2
=1􏰄 ∂ bi−􏰄aijxj 2∂xk 
i=1 j=1 mn

=􏰄 bi−􏰄aijxj (−aik)
i=1 j=1
Copyright © 2021 N. Nedialkov. All rights reserved. 7/9

Example: linear least squares fit Solving overdetermined systems Normal equations
Solve the system
mn 
0=􏰄 bi−􏰄aijxj (−aik) i=1 j=1
mmn
=−􏰄ab+􏰄a􏰄ax iki ik ijj
i=1 i=1 j=1
mnm
􏰄a 􏰄a x =􏰄a b, k=1,…,n ik ijj iki
i=1 j=1 i=1
Copyright © 2021 N. Nedialkov. All rights reserved. 8/9

Example: linear least squares fit Solving overdetermined systems Normal equations Normal equations
• The above system is the same as ATAx = ATb
• These are called normal equations
• If A has a full-column rank (all columns are linearly
independent),
min ∥b − Ax∥2 x
has a unique solution which is the solution to (AT A)x = AT b: x = (ATA)−1ATb = A†b
• A† = (AT A)−1AT is the pseudo inverse of A
Copyright © 2021 N. Nedialkov. All rights reserved. 9/9