Lagrangian Interpolation - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Software Libraries (/forum-10.html) +--- Forum: HP-65/67/97 Software Library (/forum-12.html) +--- Thread: Lagrangian Interpolation (/thread-151.html) Pages: 1 2 |
Lagrangian Interpolation - Namir - 12-18-2013 06:04 AM Langrangian Interpolation of 3 points Usage A program prompts you to enter 3 points and the interpolated x Enter y1 and the x1 at first prompt Enter y2 and the x2 at second prompt Enter y3 and the x3 at third prompt Enter xint at fourth prompt Note calculator displays 1, 2, 3 at the first, second, and third prompt B program prompts you to enter the interpolated x Program calculates and display the value of the interpolated Y. Algorithm Code: INPUT N, array X(1..N), Y(1..N), and Xint Memory Map R00 = x1 R01 = x2 R02 = X3 R03 = y1 R04 = y2 R05 = y3 R06 = x R07 = y R08 = Product R09 = used A = I for X(I) B = J for X(J) C = I for Y(I) Source Code Code:
RE: Lagrangian Interpolation - bshoring - 03-05-2015 05:17 AM Very nice program. Just loaded it and it works very well. Thank you for posting ! Bob RE: Lagrangian Interpolation - PedroLeiva - 03-05-2015 09:33 PM (03-05-2015 05:17 AM)bshoring Wrote: Very nice program. Just loaded it and it works very well. Namir, thank you very much for your contribution. I guess it is coded for HP- 67. Could you please include a sample calculation for testing the correct entry of the programming steps. From already thank you for your time. Pedro RE: Lagrangian Interpolation - bshoring - 03-07-2015 11:49 PM A program for the HP-25 gave this example: X1=-11 Y1=121 X2=3 Y2=9 X3=2 Y3=4 X=2.5 Y=6.25 etc. You should get the same results on this program. Bob RE: Lagrangian Interpolation - Thomas Klemm - 03-08-2015 06:02 AM You could use the barycentric interpolation formula: \[ L(x) = \frac{\sum_{j=0}^k \frac{w_j}{x-x_j}y_j}{\sum_{j=0}^k \frac{w_j}{x-x_j}} \] This avoids the nested loop at the cost of 3 additional registers for the weights \(w_j\). These weights have to be computed only once for the given data-set. With only 3 points you could even unroll the loop which would probably speed up the calculation. Cheers Thomas RE: Lagrangian Interpolation - Thomas Klemm - 03-08-2015 07:58 PM This program uses the method mentioned in my previous post. Memory Map \( \begin{matrix} I & : & x \\ R_0 & : & x_1 \\ R_1 & : & x_2 \\ R_2 & : & x_3 \\ R_3 & : & y_1 \\ R_4 & : & y_2 \\ R_5 & : & y_3 \\ R_6 & : & w_1 \\ R_7 & : & w_2 \\ R_8 & : & w_3 \\ R_{S4} & : & \Sigma x \\ R_{S8} & : & \Sigma xy \\ \end{matrix} \) Code: 001 31 25 11 : LBL A Explanation Lines 001-016 are the same as in Namir's orginal program. Lines 017-036 calculate the weights \(w_j = \frac{1}{\prod_{i=0,i \neq j}^k(x_j-x_i)}\). However this formula is slightly changed so that we only need the differences \(x_1-x_2\), \(x_2-x_3\) and \(x_3-x_1\): \(w_1=\frac{-1}{(x_1-x_2)(x_3-x_1)}\) \(w_2=\frac{-1}{(x_2-x_3)(x_1-x_2)}\) \(w_3=\frac{-1}{(x_3-x_1)(x_2-x_3)}\) As you can see the same factor can be used in two of the weights. Nothing fancy it's just to get the sign correct. That's why we start with \(-1\) in lines 017-021. Lines 043-063 recall \(y_j\) and calculate \(\frac{w_j}{x-x_j}\) and then use \(\Sigma +\) to calculate both \(\sum_{j=0}^k \frac{w_j}{x-x_j}\) and \(\sum_{j=0}^k \frac{w_j}{x-x_j}y_j\) in one single step. Lines 065-067 finally recall these values and calculate \(\frac{\Sigma xy}{\Sigma x}\). Cheers Thomas For those with a HP-15C here's the corresponding program: Code: 001 - 42,21,11 LBL A Added a card of the program that can be used with Jacques Laporte's HP-67 Microcode Simulator. RE: Lagrangian Interpolation - bshoring - 03-09-2015 03:30 AM Thomas, I assume pressing Keys A & B are the same as in Namir's, am I right? However after entering three data pairs, when I enter an X value and press B I am getting an Error message. For example, if I enter these X & Y values: 100 Enter 1 105 Enter 2 110.25 Enter 3 and then press 1 B, I either get an error message or get a number like 0.49 that doesn't correspond. With Namir's program, pressing 1 B would give me 100. I have checked and rechecked the program listing and can't find any errors. Am I entering the numbers wrong ? Thanks, Bob RE: Lagrangian Interpolation - PedroLeiva - 03-09-2015 03:37 AM (03-07-2015 11:49 PM)bshoring Wrote: A program for the HP-25 gave this example: Thank you very much Bob, I'll try the values in my HP 35s. Pedro RE: Lagrangian Interpolation - Thomas Klemm - 03-09-2015 09:36 AM (03-09-2015 03:30 AM)bshoring Wrote: I have checked and rechecked the program listing and can't find any errors. Am I entering the numbers wrong ? No. That's the problem with this formula: \(\ell_j(x) = \ell(x)\frac{w_j}{x-x_j}\) This leads to a division by 0 if \(x=x_j\). The reasoning is that you usually don't want to evaluate the interpolation at the known points. You could try a value very close to 1 instead. But I think your point is valid and it made me wonder if we could just use the Lagrange polynomials as Namir did but still unroll the loops. Thus the weights are now calculated in lines 017-031: \(w_1=\frac{y_1}{(x_1-x_2)(x_3-x_1)}\) \(w_2=\frac{y_2}{(x_2-x_3)(x_1-x_2)}\) \(w_3=\frac{y_3}{(x_3-x_1)(x_2-x_3)}\) Memory Map \( \begin{matrix} I & : & x \\ R_0 & : & x_1 \\ R_1 & : & x_2 \\ R_2 & : & x_3 \\ R_3 & : & w_1 \\ R_4 & : & w_2 \\ R_5 & : & w_3 \\ \end{matrix} \) By factoring the sum I was able to calculate it using only the stack in lines 035-057: \((x-x_2)(x-x_3)w_1+(x-x_1)(x-x_3)w_2+(x-x_1)(x-x_2)w_3=((x-x_2)w_1+(x-x_1)w_2)(x-x_3)+(x-x_1)(x-x_2)w_3\) Code: 001 31 25 11 : LBL A It made the program even a little shorter. Cheers Thomas RE: Lagrangian Interpolation - bshoring - 03-09-2015 09:50 PM Thomas, Thanks for the updated code. This works just great ! And it's fast, too. Regards, Bob RE: Lagrangian Interpolation - Thomas Klemm - 03-11-2015 08:04 AM For the sake of completeness I wrote a program using the Newton Polynomial \(N(x) = [y_0] + [y_0,y_1](x-x_0) + \cdots + [y_0,\ldots,y_k](x-x_0)(x-x_1)\cdots(x-x_{k-1})\) where \([y_0,\ldots,y_j]\) is the notation for divided differences. Code: 001 31 25 11 : LBL A It is a little shorter and maybe a little faster as well. Cheers Thomas Thanks to its extended register arithmetic the program for the HP-15C is even 10 lines shorter: Code: 001 - 42,21,11 LBL A RE: Lagrangian Interpolation - bshoring - 03-13-2015 05:33 AM Thanks, Thomas for posting the listing for the Newton polynomial. Looks nice. Haven't had time to try it yet. It also looks like it will work on an HP-25 as well as the HP-67. Regards, Bob RE: Lagrangian Interpolation - Newton Polynomial - bshoring - 04-04-2015 07:40 PM Newton Polynomial Version works just great. Thanks Thomas for posting ! Bob RE: Lagrangian Interpolation - Thomas Klemm - 03-09-2019 07:08 PM (03-13-2015 05:33 AM)bshoring Wrote: It also looks like it will work on an HP-25 as well as the HP-67. This program just fits in the 49 steps available for the HP-25: Code: 01: 01 : 1 Definition of the Polynomial Example: Find a quadratic polynomial given these 3 points: \(P_1(-5, 12)\), \(P_2(1, 13)\) and \(P_3(2, 11)\) CLEAR PRGM R/S 1.0000 12 ENTER -5 R/S 2.0000 13 ENTER 1 R/S 3.0000 11 ENTER 2 R/S These are the coefficients of the Newton polynomial: R3: 12.000000 R4: 0.166667 R5: -0.309524 This leads to the formula: \(f(x) = 12 + (x+5)(\frac{1}{6} - (x-1)\frac{13}{42})\) Interpolation of the Polynomial Example: Evaluate the polynomial at \(x=0.5\). 0.5 R/S 13.7679 Hint: You can just enter new values and hit R/S to evaluate the polynomial. Cheers Thomas RE: Lagrangian Interpolation - PedroLeiva - 03-14-2019 03:55 PM Here is my compilation for HP 25, I have not modified anything, just for your file To make things clear, in the HP 25 Application Programs manual, Chap 5 Numerical Methods: Linear interpolation, page 85. cites a program that works with two points instead of three. This means that when the function is a straight line I have to use this and when it is a curve the Lagrangian method? I apologize for my little knowledge in mathematics Pedro RE: Lagrangian Interpolation - Thomas Klemm - 03-14-2019 05:56 PM (03-14-2019 03:55 PM)PedroLeiva Wrote: This means that when the function is a straight line I have to use this and when it is a curve the Lagrangian method? You could enter a dummy point (e.g. 0 ENTER) as third point. Just make sure that the x-value is different from the other 2 points. And then clear register 5: CLx STO 5 If you evaluate now the polynomial of the previous example at \(x=2\) you get: 2 R/S 13.1667 Or then you can just shorten the existing program to: Code: 01: 01 : 1 HTH Thomas PS: You could also use the mid-point of the first two points as a third point. This would lead to a "natural" way to make the entry in register 5 equal to 0. RE: Lagrangian Interpolation - PedroLeiva - 03-14-2019 07:22 PM Both altrnatives (0 ENTER Xn) plus Clx STO 5, or (12,5 ENTER -2) gives me the same results as yours: 13.1667. So it works as you suggest. So this is a way to use Lagrangian for linear interpolation (1st. order polynomials), only two points. For 2nd order polynomials we can use your program, just loading three points; so we cannot use it for 3rd. or 4th. order, considering we will need 4 or 5 points. Am I right? Pedro RE: Lagrangian Interpolation - Thomas Klemm - 03-14-2019 07:58 PM (03-14-2019 07:22 PM)PedroLeiva Wrote: so we cannot use it for 3rd. or 4th. order, considering we will need 4 or 5 points. Am I right? Correct. In this case you could use (42S) Newton Polynomial Interpolation. It allows to enter as many points as you like and memory allows. Given the restrictions of the HP-25 I'm afraid we can't go further than 3 points. Cheers Thomas RE: Lagrangian Interpolation - PedroLeiva - 03-14-2019 08:12 PM I think I was asking HP25 too much. Anyway, I found that the example of the manual for linear interpolation works very well in both cases…………. Example from HP 25 Application Programs, Chapter 5 Numerical Methods/Linear Interpolation: p86 Given f(7.3)= 1.9879 f(7.4)= 2.0015 find by linear interpolation f(7.37) A. CLEAR PRGM R/S 1.0000 1.9879 ENTER 7.3 R/S 2.0000 2.0015 ENTER 7.4 R/S 3.0000 0 ENTER 7 [R/S] CLx STO 5 7.37 [R/S] 1.9974 B. CLEAR PRGM R/S 1.0000 1.9879 ENTER 7.3 R/S 2.0000 2.0015 ENTER 7.4 R/S 3.0000 1.9947 [ENTER] 7.35 [R/S] 7.37 [R/S] 1.9974 I appreciate your attention, Pedro RE: Lagrangian Interpolation - Thomas Klemm - 07-23-2022 10:20 AM (03-14-2019 08:12 PM)PedroLeiva Wrote: Example from HP 25 Application Programs, Chapter 5 Numerical Methods/Linear Interpolation: p86 For those who want to give it a try: Code: 01: 23 04 : STO 4 References
|