dichotomie.ts 14.10 KiB
// import { XOR, BoolIdentity, Debug, Result, ResultCode, UndefinedError } from "./base";
import { XOR, BoolIdentity, Debug, Result } from "./base";
import { ErrorMessage, ErrorCode } from "./util/error";
import { Nub } from "./nub";
import { ParamDefinition, ParamDomain, ParamDomainValue } from "./param"
/**
 * couple de valeurs non ordonnées
 */
class Pair {
    protected _val1: number;
    protected _val2: number;
    constructor(v1: number, v2: number) {
        this.setValues(v1, v2);
    get val1() {
        return this._val1;
    get val2() {
        return this._val2;
    setValues(v1: number, v2: number) {
        this._val1 = v1;
        this._val2 = v2;
    setPair(p: Pair) {
        this.setValues(p._val1, p._val2);
    undefine() {
        this._val1 = undefined;
        this._val2 = undefined;
    get min() {
        return Math.min(this._val1, this._val2);
    get max() {
        return Math.max(this._val1, this._val2);
    intervalHasValue(v: number) {
        return this.min <= v && v <= this.max;
/**
 * couple de valeurs ordonnées
class Interval extends Pair {
    constructor(bound1: number, bound2: number) {
        super(bound1, bound2);
    checkValue(v: number) {
        if (v == undefined) {
            let e = new ErrorMessage(ErrorCode.ERROR_INTERVAL_UNDEF);
            throw e;
        if (!this.intervalHasValue(v)) {
            let e = new ErrorMessage(ErrorCode.ERROR_INTERVAL_OUTSIDE);
            e.extraVar["value"] = v;
            e.extraVar["interval"] = this.toString();
7172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140
throw e; } } get length(): number { return this.max - this.min; } intersect(i: Interval): Interval { let min = Math.max(this.min, i.min); let max = Math.min(this.max, i.max); return new Interval(min, max); } setBounds(i: Pair) { this.setPair(i); } toString(): string { return "[" + this.min + "," + this.max + "]"; } } class SearchInterval extends Interval { private _step: number; private _dicho: Dichotomie; private _targets: Pair; constructor(d: Dichotomie, min: number, max: number, s: number) { super(min, max); if (s == 0) { let e = new ErrorMessage(ErrorCode.ERROR_DICHO_NULL_STEP); throw e; } this._step = s; this._dicho = d; } reverse() { this._step = -this._step; } growStep(k: number) { if (k == 0) { let e = new ErrorMessage(ErrorCode.ERROR_DICHO_INVALID_STEP_GROWTH); throw e; } this._step *= k; } get step() { return this._step; } get targets() { if (this._targets == undefined) this._targets = new Pair(undefined, undefined); return this._targets; } private updateTargets() { let t1 = this.targets.val1; if (t1 == undefined) t1 = this._dicho.CalculX(this._val1).vCalc let t2 = this.targets.val2; if (t2 == undefined) t2 = this._dicho.CalculX(this._val2).vCalc;
141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210
this.targets.setValues(t1, t2); } /** * get target value for lower bound */ get targetLower() { this.updateTargets(); return this.targets.val1; } /** * get target value for upper bound */ get targetUpper() { this.updateTargets(); return this.targets.val2; } next() { if (this._step > 0) { this._val1 = this._val2; this._val2 += this._step; this.targets.setValues(this.targets.val2, undefined); } else { this._val2 = this._val1; this._val1 += this._step; this.targets.setValues(undefined, this.targets.val1); } } hasTargetValue(targ: number) { this.updateTargets(); return this.targets.intervalHasValue(targ); } // isIncreasingFunction(): boolean { // non fiable : certaines fonctions (coef section puiss par ex) sont globalement monotones mais peuvent inverser localement leur sens de variation // return this.targetUpper > this.targetLower; // } } /** * calcul par dichotomie */ export class Dichotomie extends Debug { /** * définition de la variable de la fonction */ private _paramX: ParamDefinition; /** * nombre d'étapes de recherche de l'intervalle de départ */ private _startIntervalMaxSteps = 100; /** * Construction de la classe. * @param nub Noeud de calcul contenant la méthode de calcul Equation * @param sVarCalc Nom de la variable à calculer */ constructor(private nub: Nub, private sVarCalc: string, dbg: boolean = false) { super(dbg); this._paramX = this.nub.getParameter(this.sVarCalc); } /** * Valeur inconnue à rechercher
211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280
*/ get vX(): number { return this.paramX.v; } set vX(vCalc: number) { this.paramX.v = vCalc; } get paramX() { return this._paramX; } /** * étapes de recherche de l'intervalle de départ */ get startIntervalMaxSteps() { return this._startIntervalMaxSteps; } set startIntervalMaxSteps(n: number) { this._startIntervalMaxSteps = n; } /** * Calcul de l'équation analytique. * @note Wrapper vers this.nub.Equation pour simplifier le code. * On utilise la première variable du tableau des variables pouvant être calculée analytiquement * Il faudra s'assurer que cette première variable correspond à la méthode de calcul la plus rapide */ private Calcul(): Result { let targetParam: ParamDefinition = this.nub.getFirstAnalyticalParameter(); let r: Result = this.nub.Equation(targetParam.symbol); this.debug("dicho : Calcul(vX=" + this.sVarCalc + "=" + this.vX + ") -> " + targetParam.symbol + "=" + r.vCalc); return r; } CalculX(x: number): Result { this.vX = x return this.Calcul(); } /** * Détermine si une fonction est croissante ou décroissante. * On fait ça en sondant plusieurs points sur un intervalle : on ne peut pas * prendre 2 valeurs de la fonction pour 2 valeurs successives de la variable car certaines * fonctions (Q=f(coef de la section puissance) par ex) ne sont pas strictement monotones (globalement * monotones mais peuvent inverser localement leur sens de variation) * @param d domaine de définition de la variable */ private isIncreasingFunction(d: ParamDomain): boolean { let n = 20; let variation = 0; let min, max, step; switch (d.domain) { case ParamDomainValue.INTERVAL: min = d.minValue; max = d.maxValue; break; case ParamDomainValue.ANY: case ParamDomainValue.NOT_NULL: min = -100; max = 100; break; case ParamDomainValue.POS: min = 1e-8; max = 200;
281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350
break; case ParamDomainValue.POS_NULL: min = 0; max = 200; break; default: throw "unsupported parameter domain value" } let x = min; step = (max - min) / n; let lastY; for (let i = 0; i < n; i++) { if (x == 0 && d.domain == ParamDomainValue.NOT_NULL) x = 1e-8; let y = this.CalculX(x).vCalc; if (i > 0) { if (y > lastY) variation++; else variation--; } lastY = y; x += step; } if (variation == 0) { let e = new ErrorMessage(ErrorCode.ERROR_DICHO_FUNCTION_VARIATION); throw e; } return variation > 0; } /** * Détermine l'intervalle de recherche initial * @param rTarget valeur cible de la fonction * @param rInit valeur initiale de la variable */ private getStartInterval(rTarget: number, rInit: number): any { let prmDom: ParamDomain = this.paramX.getDomain(); let min, max, step; switch (prmDom.domain) { case ParamDomainValue.INTERVAL: min = prmDom.minValue; max = prmDom.maxValue; step = (max - min) / 100.0; break; case ParamDomainValue.ANY: min = -Infinity; max = Infinity; step = 1; break; case ParamDomainValue.NOT_NULL: min = -Infinity; max = Infinity; step = 1; if (rInit == 0) rInit = 1e-8; break; case ParamDomainValue.POS: min = 1e-8;
351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420
max = Infinity; step = 1; break; case ParamDomainValue.POS_NULL: min = 0; max = Infinity; step = 1; break; default: throw "unsupported parameter domain value"; } let intMax: Interval = new Interval(min, max); intMax.checkValue(rInit); let intSearch: SearchInterval = new SearchInterval(this, rInit, rInit + step, step); let inc = this.isIncreasingFunction(prmDom); let initTarget = this.CalculX(rInit).vCalc; // if (initTarget > rTarget && inc || initTarget < rTarget && !inc) if (BoolIdentity(initTarget > rTarget, inc)) intSearch.reverse(); let n = 0; let ok: boolean = false; do { var inters: Interval = intSearch.intersect(intMax); if (inters.length == 0) break; intSearch.setBounds(inters); if (intSearch.hasTargetValue(rTarget)) { ok = true; break; } intSearch.growStep(2); intSearch.next(); } while (n++ < this._startIntervalMaxSteps); // intervalle trouvé if (ok) return { ok, intSearch }; // la valeur cible de la fonction est elle trouvable ? let aps: string = this.nub.getFirstAnalyticalParameter().symbol; let m; let res: ErrorMessage; let errDomain = false; switch (prmDom.domain) { case ParamDomainValue.INTERVAL: let si: SearchInterval = new SearchInterval(this, intMax.min, intMax.max, 1); errDomain = !si.hasTargetValue(rTarget); break; case ParamDomainValue.POS: case ParamDomainValue.POS_NULL: let y = this.CalculX(1e-8).vCalc; errDomain = inc && (rTarget < y); break; case ParamDomainValue.ANY: break; default: throw "unsupported parameter domain value";
421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490
} if (errDomain) { res = new ErrorMessage(ErrorCode.ERROR_DICHO_INIT_DOMAIN); res.extraVar["targetSymbol"] = aps; // symbole de la variable calculée par la fonction res.extraVar["targetValue"] = rTarget; // valeur cible pour la fonction res.extraVar["variableInterval"] = intMax.toString(); // intervalle de valeurs pour la variable d'entrée de la fonction res.extraVar["variableSymbol"] = this.paramX.symbol; // symbole de la variable d'entrée de la fonction } else { if (intSearch.step < 0) res = new ErrorMessage(ErrorCode.ERROR_DICHO_INITVALUE_HIGH); else res = new ErrorMessage(ErrorCode.ERROR_DICHO_INITVALUE_LOW); res.extraVar["variableSymbol"] = this.paramX.symbol; // symbole de la variable de la fonction res.extraVar["variableInitValue"] = rInit; // valeur initiale de la variable res.extraVar["targetSymbol"] = aps; // symbole de la variable calculée par la fonction res.extraVar["targetValue"] = rTarget; // valeur cible pour la fonction res.extraVar["initTarget"] = initTarget; // valeur de la fonction pour la valeur initiale de la variable } return { ok, res }; } /** * @param Xmin valeur min de l'intervalle * @param Xmax valeur max de l'intervalle * @param Y valeur cible de la fonction * @param Ymin valeur de la fonction pour Xmin * @param Ymax valeur de la fonction pour Xmax */ private dichoSearch(Ytarg: number, rTol: number, Xmin: number, Xmax: number, Ymin: number, Ymax: number): Result { let Xmid = (Xmin + Xmax) / 2; if (Math.abs(Xmin - Xmax) <= rTol) return new Result(Xmid); let Ymid = this.CalculX(Xmid).vCalc; if (Ymin < Ymax) { // fonction croissante if (Ytarg > Ymid) return this.dichoSearch(Ytarg, rTol, Xmid, Xmax, Ymid, Ymax); // intervalle supérieur return this.dichoSearch(Ytarg, rTol, Xmin, Xmid, Ymin, Ymid); // intervalle inférieur } else { // fonction décroissante if (Ytarg > Ymid) return this.dichoSearch(Ytarg, rTol, Xmin, Xmid, Ymin, Ymid); // intervalle inférieur return this.dichoSearch(Ytarg, rTol, Xmid, Xmax, Ymid, Ymax); // intervalle supérieur } } Dichotomie(rTarget: number, rTol: number, rInit: number): Result { // console.log("-----"); // for (let x = 0; x <= 1; x += 0.1) // console.log(this.CalculX(x).vCalc); // console.log("-----"); // recherche de l'intervalle de départ this.debug("intervalle de départ"); let r = this.getStartInterval(rTarget, rInit); if (r.ok) var interv: SearchInterval = r.intSearch; else { let result = new Result(undefined, r.res); return result;
491492493494495496497498499
} // Dichotomie this.debug("start dicho"); return this.dichoSearch(rTarget, rTol, interv.min, interv.max, interv.targetLower, interv.targetUpper); } }