18.5 Linear Regularization Methods 809 since it is so obviously a good idea.)In its simplest form,the method is an immediate generalization of zeroth-order regularization (equation 18.4.11,above).As before, the functional A is taken to be the x2 deviation,equation(18.4.9),but the functional B is replaced by more sophisticated measures of smoothness that derive from first or higher derivatives. For example,suppose that your a priori belief is that a credible u()is not too different from a constant.Then a reasonable functional to minimize is M-1 Bx/位(2dx∑位u-立u+1]2 (18.5.1) 4=1 since it is nonnegative and equal to zero only when (z)is constant.Here =()and the second equality (proportionality)assumes that the a's are uniformly spaced.We can write the second form of B as B=B.2=.(BT.B).=H. (18.5.2) where u is the vector of components,u=1,...,M,B is the (M-1)x M first difference matrix (Nort serve -1 100 00 0 0 -1 1 0 0 0 0 0 computer, Americ make one paper University Press. THE (18.5.3) ART 0 00 0 0 -1 1 0 0 Programs 0 0 0 0 0 -1 and H is the M×M matrix 量 1 -1 0 0 0 0 0 0 -1 2 -1 0 0 0 0 0 -1 2 -1 0 0 0 0 H=BT.B (18.5.4) OF SCIENTIFIC COMPUTING (ISBN 1988-19920 0 0 0 0 -1 2 -1 0 0 0 0 0 -1 @cambri 0 0 0 0 0 0 -1 Numerical Recipes 10-6211 Note that B has one fewer row than column.It follows that the symmetric H is degenerate:it has exactly one zero eigenvalue corresponding to the value of a constant function,any one of which makes B exactly zero. (outside If,just as in $15.4,we write North Software. Ai三Ru/o:b:≡c/o (18.5.5) then,using equation(18.4.9),the minimization principle(18.4.12)is minimize:A+B A.-b+.H. (18.5.6) This can readily be reduced to a linear set of normal equations,just as in $15.4:The components of the solution satisfy the set of M equations in M unknowns, ∑（E44)+aa=∑4 4=1,2,,M(18.5.7)18.5 Linear Regularization Methods 809 Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). since it is so obviously a good idea.) In its simplest form, the method is an immediate generalization of zeroth-order regularization (equation 18.4.11, above). As before, the functional A is taken to be the χ2 deviation, equation (18.4.9), but the functional B is replaced by more sophisticated measures of smoothness that derive from first or higher derivatives. For example, suppose that your a priori belief is that a credible u(x) is not too different from a constant. Then a reasonable functional to minimize is B ∝
[u
(x)]2dx ∝ M −1 µ=1 [uµ − uµ+1] 2 (18.5.1) since it is nonnegative and equal to zero only when u(x) is constant. Here uµ ≡ u(xµ), and the second equality (proportionality) assumes that the x µ’s are uniformly spaced. We can write the second form of B as B = |B · u| 2 = u · (BT · B) · u ≡ u · H · u (18.5.2) where u is the vector of components uµ, µ = 1,...,M, B is the (M − 1) × M first difference matrix B =   −1100000 ··· 0 0 −110000 ··· 0 . . . ... . . . 0 ··· 0000 −110 0 ··· 00000 −1 1   (18.5.3) and H is the M × M matrix H = BT · B =   1 −100000 ··· 0 −1 2 −10000 ··· 0 0 −1 2 −1000 ··· 0 . . . ... . . . 0 ··· 000 −1 2 −1 0 0 ··· 0000 −1 2 −1 0 ··· 00000 −1 1   (18.5.4) Note that B has one fewer row than column. It follows that the symmetric H is degenerate; it has exactly one zero eigenvalue corresponding to the value of a constant function, any one of which makes B exactly zero. If, just as in §15.4, we write Aiµ ≡ Riµ/σi bi ≡ ci/σi (18.5.5) then, using equation (18.4.9), the minimization principle (18.4.12) is minimize: A + λB = |A · u − b| 2 + λu · H · u (18.5.6) This can readily be reduced to a linear set of normal equations, just as in §15.4: The components uµ of the solution satisfy the set of M equations in M unknowns, ρ  i AiµAiρ + λHµρ uρ = i Aiµbi µ = 1, 2,...,M (18.5.7)