File: solvers.chapt.txt

package info (click to toggle)
yacas 1.3.6-2
  • links: PTS
  • area: main
  • in suites: bullseye, buster, sid, stretch
  • size: 7,176 kB
  • ctags: 3,520
  • sloc: cpp: 13,960; java: 12,602; sh: 11,401; makefile: 552; perl: 517; ansic: 381
file content (430 lines) | stat: -rw-r--r-- 11,552 bytes parent folder | download | duplicates (5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430

			Symbolic solvers

*INTRO By solving one tries to find a mathematical object that meets certain criteria. This chapter documents the functions that are available to help find solutions to specific types of problems.


*CMD Solve --- solve an equation
*STD
*CALL
	Solve(eq, var)

*PARMS

{eq} -- equation to solve

{var} -- variable to solve for

*DESC

This command tries to solve an equation. If {eq} does not contain the
{==} operator, it is assumed that the user wants to solve $eq ==
0$. The result is a list of equations of the form {var == value}, each
representing a solution of the given equation. The {Where} operator
can be used to substitute this solution in another expression. If the
given equation {eq} does not have any solutions, or if {Solve} is
unable to find any, then an empty list is returned.

The current implementation is far from perfect. In particular, the
user should keep the following points in mind:
*	{Solve} cannot solve all equations. If it is given a equation
it can not solve, it raises an error via {Check}. Unfortunately, this
is not displayed by the inline pretty-printer; call {PrettyPrinter'Set} to
change this. If an equation cannot be solved analytically, you may
want to call {Newton} to get a numerical solution.
*	Systems of equations are not handled yet. For linear systems,
{MatrixSolve} can be used. The old version of {Solve}, with the name
{OldSolve} might be able to solve nonlinear systems of equations.
*	The periodicity of the trigonometric functions {Sin}, {Cos},
and {Tan} is not taken into account. The same goes for the (imaginary)
periodicity of {Exp}. This causes {Solve} to miss solutions.
*	It is assumed that all denominators are nonzero. Hence, a
solution reported by {Solve} may in fact fail to be a solution because
a denominator vanishes.
*	In general, it is wise not to have blind trust in the results
returned by {Solve}. A good strategy is to substitute the solutions
back in the equation.

*E.G. notest

First a simple example, where everything works as it should. The
quadratic equation $x^2 + x == 0$ is solved. Then the result is
checked by substituting it back in the quadratic.

	In> quadratic := x^2+x;
	Out> x^2+x;
	In> Solve(quadratic, x);
	Out> {x==0,x==(-1)};
	In> quadratic Where %;
	Out> {0,0};

If one tries to solve the equation $Exp(x) == Sin(x)$, one finds that
{Solve} can not do this.

	In> PrettyPrinter'Set("DefaultPrint");
	Out> True;
	In> Solve(Exp(x) == Sin(x), x);
	Error: Solve'Fails: cannot solve equation Exp(x)-Sin(x) for x
	Out> {};

The equation $Cos(x) == 1/2$ has an infinite number of solutions,
namely $x == (2*k + 1/3) * Pi$ and $x == (2*k - 1/3) * Pi$ for any
integer $k$. However, {Solve} only reports the solutions with $k == 0$.

	In> Solve(Cos(x) == 1/2, x);
	Out> {x==Pi/3,x== -Pi/3};

For the equation $x/Sin(x) == 0$, a spurious solution at $x == 0$ is
returned. However, the fraction is undefined at that point.

	In> Solve(x / Sin(x) == 0, x);
	Out> {x==0};

At first sight, the equation $Sqrt(x) == a$ seems to have the solution
$x == a^2$. However, this is not true for eg. $a == -1$.

	In> PrettyPrinter'Set("DefaultPrint");
	Out> True;
	In> Solve(Sqrt(x) == a, x);
	Error: Solve'Fails: cannot solve equation Sqrt(x)-a for  x
	Out> {};
	In> Solve(Sqrt(x) == 2, x);
	Out> {x==4};
	In> Solve(Sqrt(x) == -1, x);
	Out> {};

*SEE Check, MatrixSolve, Newton, OldSolve, PrettyPrinter'Set, PSolve, Where, ==

*CMD OldSolve --- old version of {Solve}
*STD
*CALL
	OldSolve(eq, var)
	OldSolve(eqlist, varlist)

*PARMS

{eq} -- single identity equation

{var} -- single variable

{eqlist} -- list of identity equations

{varlist} -- list of variables

*DESC

This is an older version of {Solve}. It is retained for two
reasons. The first one is philosophical: it is good to have multiple
algorithms available. The second reason is more practical: the newer
version cannot handle systems of equations, but {OldSolve} can.

This command tries to solve one or more equations. Use the first form
to solve a single equation and the second one for systems of
equations.

The first calling sequence solves the equation "eq" for the variable
"var". Use the {==} operator to form the equation.
The value of "var" which satisfies the equation, is returned. Note
that only one solution is found and returned.

To solve a system of equations, the second form should be used. It
solves the system of equations contained in the list "eqlist" for
the variables appearing in the list "varlist". A list of results is
returned, and each result is a list containing the values of the
variables in "varlist". Again, at most a single solution is
returned.

The task of solving a single equation is simply delegated to {SuchThat}. Multiple equations are solved recursively:
firstly, an equation is sought in which one of the variables occurs
exactly once; then this equation is solved with {SuchThat}; and finally the solution is substituted in the
other equations by {Eliminate} decreasing the number
of equations by one. This suffices for all linear equations and a
large group of simple nonlinear equations.

*E.G.

	In> OldSolve(a+x*y==z,x)
	Out> (z-a)/y;
	In> OldSolve({a*x+y==0,x+z==0},{x,y})
	Out> {{-z,z*a}};

This means that "x = (z-a)/y" is a solution of the first equation
and that "x = -z", "y = z*a" is a solution of the systems of
equations in the second command.

An example which {OldSolve} cannot solve:

	In> OldSolve({x^2-x == y^2-y,x^2-x == y^3+y},{x,y});
	Out> {};

*SEE Solve, SuchThat, Eliminate, PSolve, ==

*CMD SuchThat --- special purpose solver
*STD
*CALL
	SuchThat(expr, var)

*PARMS

{expr} -- expression to make zero

{var} -- variable (or subexpression) to solve for

*DESC

This functions tries to find a value of the variable "var" which
makes the expression "expr" zero. It is also possible to pass a
subexpression as "var", in which case {SuchThat}
will try to solve for that subexpression.

Basically, only expressions in which "var" occurs only once are
handled; in fact, {SuchThat} may even give wrong
results if the variables occurs more than once. This is a consequence
of the implementation, which repeatedly applies the inverse of the top
function until the variable "var" is reached.

*E.G.

	In> SuchThat(a+b*x, x)
	Out> (-a)/b;
	In> SuchThat(Cos(a)+Cos(b)^2, Cos(b))
	Out> Cos(a)^(1/2);
	In> A:=Expand(a*x+b*x+c, x)
	Out> (a+b)*x+c;
	In> SuchThat(A, x)
	Out> (-c)/(a+b);

*SEE Solve, OldSolve, Subst, Simplify

*CMD Eliminate --- substitute and simplify
*STD
*CALL
	Eliminate(var, value, expr)

*PARMS

{var} -- variable (or subexpression) to substitute

{value} -- new value of "var"

{expr} -- expression in which the substitution should take place

*DESC

This function uses {Subst} to replace all instances
of the variable (or subexpression) "var" in the expression "expr"
with "value", calls {Simplify} to simplify the
resulting expression, and returns the result.

*E.G.

	In> Subst(Cos(b), c) (Sin(a)+Cos(b)^2/c)
	Out> Sin(a)+c^2/c;
	In> Eliminate(Cos(b), c, Sin(a)+Cos(b)^2/c)
	Out> Sin(a)+c;

*SEE SuchThat, Subst, Simplify

*CMD PSolve --- solve a polynomial equation
*STD
*CALL
	PSolve(poly, var)

*PARMS

{poly} -- a polynomial in "var"

{var} -- a variable

*DESC

This commands returns a list containing the roots of "poly",
considered as a polynomial in the variable "var". If there is only
one root, it is not returned as a one-entry list but just by
itself. A double root occurs twice in the result, and similarly for
roots of higher multiplicity. All polynomials of degree up to 4 are
handled.

*E.G.

	In> PSolve(b*x+a,x)
	Out> -a/b;
	In> PSolve(c*x^2+b*x+a,x)
	Out> {(Sqrt(b^2-4*c*a)-b)/(2*c),(-(b+
	Sqrt(b^2-4*c*a)))/(2*c)};

*SEE Solve, Factor

*CMD MatrixSolve --- solve a system of equations
*STD
*CALL
	MatrixSolve(A,b)

*PARMS

{A} -- coefficient matrix

{b} -- row vector

*DESC

{MatrixSolve} solves the matrix equations {A*x = b} using Gaussian Elimination
with Backward substitution. If your matrix is triangular or diagonal, it will
be recognized as such and a faster algorithm will be used.

*E.G.

	In> A:={{2,4,-2,-2},{1,2,4,-3},{-3,-3,8,-2},{-1,1,6,-3}};
	Out> {{2,4,-2,-2},{1,2,4,-3},{-3,-3,8,-2},{-1,1,6,-3}};
	In> b:={-4,5,7,7};
	Out> {-4,5,7,7};
	In> MatrixSolve(A,b);
	Out> {1,2,3,4};



			Numeric solvers

*CMD Newton --- solve an equation numerically with Newton's method
*STD
*CALL
	Newton(expr, var, initial, accuracy)
	Newton(expr, var, initial, accuracy,min,max)

*PARMS

{expr} -- an expression to find a zero for

{var} -- free variable to adjust to find a zero

{initial} -- initial value for "var" to use in the search

{accuracy} -- minimum required accuracy of the result

{min} -- minimum value for "var" to use in the search

{max} -- maximum value for "var" to use in the search

*DESC

This function tries to numerically find a zero of the expression
{expr}, which should depend only on the variable {var}. It uses
the value {initial} as an initial guess.

The function will iterate using Newton's method until it estimates
that it has come within a distance {accuracy} of the correct
solution, and then it will return its best guess. In particular, it
may loop forever if the algorithm does not converge.

When {min} and {max} are supplied, the Newton iteration takes them
into account by returning {Fail} if it failed to find a root in
the given range. Note this doesn't mean there isn't a root, just
that this algorithm failed to find it due to the trial values
going outside of the bounds.

*E.G.

	In> Newton(Sin(x),x,3,0.0001)
	Out> 3.1415926535;
	In> Newton(x^2-1,x,2,0.0001,-5,5)
	Out> 1;
	In> Newton(x^2+1,x,2,0.0001,-5,5)
	Out> Fail;

*SEE Solve, NewtonNum



*CMD FindRealRoots --- find the real roots of a polynomial
*STD
*CALL
	FindRealRoots(p)

*PARMS

{p} - a polynomial in {x}

*DESC

Return a list with the real roots of $ p $. It tries to find the real-valued
roots, and thus requires numeric floating point calculations. The precision
of the result can be improved by increasing the calculation precision.

*E.G. notest

	In> p:=Expand((x+3.1)^5*(x-6.23))
	Out> x^6+9.27*x^5-0.465*x^4-300.793*x^3-
	1394.2188*x^2-2590.476405*x-1783.5961073;
	In> FindRealRoots(p)
	Out> {-3.1,6.23};

*SEE SquareFree, NumRealRoots, MinimumBound, MaximumBound, Factor



*CMD NumRealRoots --- return the number of real roots of a polynomial
*STD
*CALL
	NumRealRoots(p)

*PARMS

{p} - a polynomial in {x}

*DESC

Returns the number of real roots of a polynomial $ p $.
The polynomial must use the variable {x} and no other variables.

*E.G.

	In> NumRealRoots(x^2-1)
	Out> 2;
	In> NumRealRoots(x^2+1)
	Out> 0;

*SEE FindRealRoots, SquareFree, MinimumBound, MaximumBound, Factor

*CMD MinimumBound --- return lower bounds on the absolute values of real roots of a polynomial
*CMD MaximumBound --- return upper bounds on the absolute values of real roots of a polynomial
*STD
*CALL
	MinimumBound(p)
	MaximumBound(p)

*PARMS

{p} - a polynomial in $x$

*DESC

Return minimum and maximum bounds for the absolute values of the real
roots of a polynomial {p}. The polynomial has to be converted to one with
rational coefficients first, and be made square-free.
The polynomial must use the variable {x}.

*E.G.

	In> p:=SquareFree(Rationalize((x-3.1)*(x+6.23)))
	Out> (-40000*x^2-125200*x+772520)/870489;
	In> MinimumBound(p)
	Out> 5000000000/2275491039;
	In> N(%)
	Out> 2.1973279236;
	In> MaximumBound(p)
	Out> 10986639613/1250000000;
	In> N(%)
	Out> 8.7893116904;

*SEE SquareFree, NumRealRoots, FindRealRoots, Factor





*INCLUDE logic.chapt

*INCLUDE ode.chapt